LeetCode Q 204 - Count Primes
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.
Solution
Code:
public int countPrimes(int n) {
boolean[] seen = new boolean[n];
int res = 0;
for (int i = 2; i < n; i++) {
if (!seen[i]) {
res++;
for (int num = 2; num * i < n; num++)
seen[num * i] = true;
}
}
return res;
}