204. Count Primes

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int countPrimes(int n) {
        boolean[] numbers = new boolean[n + 1];
        
        for (int p = 2; p <= (int) Math.sqrt(n); p++) {
            if (numbers[p] == false) {
                for (int j = p + p; j < n; j += p) {
                    numbers[j] = true;
                }
            } 
        }
        
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (numbers[i] == false) {
                count++;
            }
        }
        return count;
    }
}