Leetcode: Count Primes

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

Algorithm: The sieve of Eratosthenes, Referring to Summary: Primes

0 and 1 are not primes!

Maintain a notPrime boolean array. Start from the first prime 2, cross out all its multiples. The next number that is not crossed out is the next prime. Continue the process until reach n.

 1 public class Solution {
 2     public int countPrimes(int n) {
 3         if (n <= 1) return 0;
 4         boolean[] notPrime = new boolean[n+1];
 5         notPrime[0] = true;
 6         notPrime[1] = true;
 7         int count = 0;
 8         for (int i=2; i<n; i++) {
 9             if (!notPrime[i]) {
10                 count++;
11                 int mul = 2;
12                 while (i <= n/mul) {
13                     notPrime[i*mul] = true;
14                     mul++;
15                 }
16             }
17         }
18         return count;
19     }
20 }