LeetCode OJ: 204. Count Primes 計算質數個數

若您覺得文章寫得不錯，請點選文章上的廣告，來支持小編，謝謝。

題目連結，此題在Wiki上有個埃拉托斯特尼篩法：

Input: an integer n > 1
 
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
 
 for i = 2, 3, 4, ..., not exceeding √n:
  if A[i] is true:
    for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
      A[j] := false
 
Output: all i such that A[i] is true.

Wiki上還有動畫說明：

public class Solution {
 public int countPrimes(int n) {
   boolean[] primes = new boolean[n];
  
  for(int i = 2; i < n; i++)
   primes[i] = true;
  
  for(int i = 2; i * i < n; i++) {
   if( primes[i] )
    for(int j = i * i; j < n; j = j + i)
     primes[j] = false;
  }
  
  int primeCnt = 0;
  for(int i = 0; i < n; i++)
   if(primes[i])
    primeCnt++;
  
  return primeCnt;
 }
}