Count the number of prime numbers less than a non-negative number, n.

```public class Solution {
public int countPrimes(int n) {
}
}```

This problem is selected from LeetCode.

Solution

The magnification of a number must not be a prime number. So from each number i from 2 to n, we mark all the numbers from i+1 to n that are magnifications of i to non-primes. Each time, we check if i is marked as non-prime. If not, it must be a prime.

Here is a small optimization. Let’s write down all of 12’s factors:

```2 × 6 = 12
3 × 4 = 12
4 × 3 = 12
6 × 2 = 12```

As you can see, calculations of 4 × 3 and 6 × 2 are not necessary. Therefore, we only need to consider factors up to √n because, if n is divisible by some number p, then n = p × q and since p ≤ q, we could derive that p ≤ √n.

The following is the code for the method:

```public int countPrimes(int n) {
boolean[] isPrime = new boolean[n];
for (int i = 2; i < n; i++) {
isPrime[i] = true;
}
// Loop's ending condition is i * i < n instead of i < sqrt(n)
// to avoid repeatedly calling an expensive function sqrt().
for (int i = 2; i * i < n; i++) {
if (!isPrime[i]) continue;
for (int j = i * i; j < n; j += i) {
isPrime[j] = false;
}
}

int count = 0;
for (int i = 2; i < n; i++) {
if (isPrime[i]) count++;
}
return count;
}```