``````class Solution {
public:
int countPrimes(int n) {
int cnt = 0;
for(int i = 2;i < n;i++)
{
if(isPrime(i))
cnt++;
}

return cnt;
}
private:
bool isPrime(int n) {
for(int i = 2;i <= n/2;i++)
{
if(n % i == 0)
return false;
}
return true;
}
};``````

``````17 / 20 test cases passed.
Status: Time Limit Exceeded
Submitted: 0 minutes ago``````
``````/*
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
A[j] := false

return all i such that A[i] is true.
*/
class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
int cnt = n - 2;
vector<bool> prime(n,true);
prime[0] = prime[1] = false;
for(int i = 2;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);
}
};``````

``````Runtime: 180 ms, faster than 42.90% of C++ online submissions for Count Primes.
Memory Usage: 6.5 MB, less than 7.72% of C++ online submissions for Count Primes.``````

``````/*
algorithm Sieve of Eratosthenes is
input: an integer n > 1.
output: all prime numbers from 2 through n.

let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.

for i = 2, 3, 4, ..., not exceeding √n do
if A[i] is true
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n do
A[j] := false

return all i such that A[i] is true.
*/
class Solution {
public:
int countPrimes(int n) {
if(n <= 2) return 0;
int cnt = n - 2;
vector<bool> prime(n,true);
prime[0] = prime[1] = false;
for(int i = 2;i < sqrt(n);i++)
{
if(prime[i])
{
for(int j = i * i;j < n;j += i)
{
if(prime[j])
cnt--;
prime[j] = false;
}
}
}

return cnt;
}
};``````

``````20 / 20 test cases passed.
Status: Accepted
Runtime: 232 ms
Memory Usage: 6.7 MB``````