# 204. Count Primes
Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
# Solution
Approach 1: A number's times are not prime.
# Code (Python)
Approach 1:
# Code (C++)
Approach 1:
class Solution {
public:
int countPrimes(int n) {
if (n <= 2) return 0;
bool isPrime[n];
for (int i = 0; i < n; ++i)
{
isPrime[i] = true;
}
isPrime[0] = 0;
isPrime[1] = 0;
for (int i = 2; i * i < n; ++i)
{
for (int j = 2; j * i < n; ++j)
{
isPrime[j * i] = false;
}
}
int numOfPrime = 0;
for (int i = 0; i < n; ++i)
{
if (isPrime[i]) numOfPrime++;
}
return numOfPrime;
}
};