P191 质数的个数

描述#

这个题目说的是，给你一个非负整数 n，你要计算出小于 n 的质数（素数）一共有多少个。

比如说，给你的 n 等于 8：
n = 8
小于 8 的质数一共有 4 个，分别是：
2, 3, 5, 7
因此你要返回 4。

代码#

public class AlgoCasts {

  // Time: O(n*log(log(n))), Space: O(n)
  public int countPrimesSieve(int n) {
    if (n <= 2) return 0;
    boolean[] primes = new boolean[n];
    Arrays.fill(primes, true);
    primes[0] = false; primes[1] = false;
    int upper = (int) Math.sqrt(n);
    for (int i = 2; i <= upper; ++i) {
      if (primes[i])
        for (int j = i*i; j < n; j += i) primes[j] = false;
    }
    int cnt = 0;
    for (boolean prime: primes)
      if (prime) ++cnt;
    return cnt;
  }

  // Time: O(n*log(log(n))), Space: O(n)
  public int countPrimesSieveFast(int n) {
    if (n <= 2) return 0;
    boolean[] composites = new boolean[n];
    int upper = (int) Math.sqrt(n);
    int cnt = 1;
    for (int i = 3; i < n; i += 2) {
      if (composites[i]) continue;
      ++cnt;
      if (i > upper) continue;
      for (int j = i*i; j < n; j += 2*i) composites[j] = true;
    }
    return cnt;
  }

}