204. Count Primes

Description

Here

Discussion

It's really not hard to find out 2 ways to solve it.

1. loop [1, n), check if isPrime(int n) and count
2. Using dp, when we found one prime, mark all the multiples to invalid

Slow Solution

public int countPrimes(int n) {
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (isPrime(i))
      count++;
  }
  return count;
}

private static boolean isPrime(int i) {
  if (i < 2) {
    return false;
  } else if (i == 2) {
    return true;
  } else {
    for (int factor = 2; factor <= i / factor; factor++) {
      if (i % factor == 0) {
        return false;
      }
    }
  }
  return true;
}

Dp Solution

public int countPrimes(int n) {
  final boolean[] isNotPrime = new boolean[n];
  int count = 0;
  for (int i = 2; i < n; i++) {
    if (!isNotPrime[i]) {
      count++;
      for (int j = 2; j * i < n; j++) {
        isNotPrime[i * j] = true;
      }
    }
  }
  return count;
}

Reason Why the Second One is Faster

When you mark one number to invalid prime, the prime check loop won't be there.