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; }

## Leave A Comment