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

RelatedPost