Count the number of prime numbers less than a non-negative number, n
Solution I (Iterating till √n)
class Solution
{
public:
bool isPrime(int n)
{
int p=0;
for (int i = 2; i*i<=n; i++)
{
int x = n % i;
if (x == 0)
{
p = p + 1;
}
}
if (p == 0)
{
return true;
}
else
{
return false;
}
}
int countPrimes(int n)
{
int s = 0;
for (int i = 2; i < n; i++)
{
if (isPrime(i))
{
s = s + 1;
}
}
return s;
}
};
Time complexity: O(√n)
Prime Sieve Method (Sieve of Eratosthenes)
class Solution
{
public:
int countPrimes(int n)
{
int s = 0;
vector<bool> v(n + 1);
for (int i = 2; i < n; i++)
{
if (!v[i])
{
for (int j = i; j+i <= n; j += i)
{
v[j+i] = true;
}
}
}
for (int i = 2; i < n; i++)
{
if (!v[i])
{
s = s + 1;
}
}
return s;
}
};