# Sieve of Eratosthenes - Explanation and Assisting code in python

• A prime is anything that is not divisible by any other number other than 1 and itself.
The method is:

1-Make a sequence of all numbers from 1 to n
2-Pick a number starting from 2 in the sequence. Let this number be i.
3-Iterate over the sequence and mark all those numbers which are 'i' numbers spaced from each other. For ex., if i=2, then mark 4,6,8,... as all these numbers cant be primes as they are all divisible by i.
4-Keep increasing 'i' till you reach the square of number i. In our example, all the numbers till now have been marked which are multiples of 2, hence no need to increase 'i' more than 'i^2'.
5-All the other numbers that have not been marked are primes.

Here is the code for reference,

``````    def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n<3:
return 0

dict_s=[1]*n
dict_s[0]=0
dict_s[1]=0
for i in range(2,n):
dict_s[i]=1
for i in range(2,int(math.sqrt(n))+1):
if dict_s[i]:
for j in range(i+i,n,i):
dict_s[j]=0
return sum(dict_s)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.