# Short C++ Sieve of Eratosthenes solution

• ``````class Solution {
public:
int countPrimes(int n) {
vector<bool> prime(n, true);
prime[0] = false, prime[1] = false;
for (int i = 0; i < sqrt(n); ++i) {
if (prime[i]) {
for (int j = i*i; j < n; j += i) {
prime[j] = false;
}
}
}
return count(prime.begin(), prime.end(), true);
}
};``````

• can you explain how to come up with this genius idea?you are smarter than too many people

• it is the Sieve of Eratosthenes algorithm, wiki: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

• Python3 Solution

``````class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n < 2:
return 0
prime = [True] * n
prime[0] = prime[1] = False
for i in range(int(math.ceil(n**0.5))):
if prime[i]:
for j in range(i**2, n, i):
prime[j] = False
return prime.count(True)
``````

• @deck seems like maintaining a counter would be better than iterating through the primes at the end

• why I am getting wrong answer? my code

``````public:
int countPrimes(int n) {
bool *a=new bool[n];
memset(a,true,sizeof(a));
a[0]=false,a[1]=false;
for(int i=2;i<sqrt(n);i++)
{
if(a[i])
{
for(int j=i*i;j<n;j+=i)
a[j]=false;
}
}
return count(a,a+n,true);
}
};`````````

• @abhinav_smart
You should notice this line`memset(a,true,sizeof(a));`, here `sizeof(a)` actually equals to `4`, which is the size of a pointer. I suppose that it should be written as `memset(a, true, sizeof(a)*n)`
Hope it will help. :)

• @wysqh Thanks Brother

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