[LeetCode] Problem 204 - Count Primes

Posted on | In ,

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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int countPrimes(int n) {
    boolean[] notPrime = new boolean[n + 1];
    int count = 0;

    for (int i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;

            for (int j = i; j <= n / i; j++)
                notPrime[i * j] = true;
        }
    }

    return count;
}