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);
}
};
Short C++ Sieve of Eratosthenes solution

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

@abhinav_smart
You should notice this linememset(a,true,sizeof(a));
, heresizeof(a)
actually equals to4
, which is the size of a pointer. I suppose that it should be written asmemset(a, true, sizeof(a)*n)
Hope it will help. :)
