Count Primes

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