LeetCode(204):カウント質量Count Primes(Java)

2.19.9.16#プログラマー筆記試験必須#LeetCodeゼロブラシ個人メモ整理(継続更新)
直接質量数の定義に従って計算するとタイムアウトが報告され、西元前250年、ギリシャの数学者エラドセ(Eeatosthese)が考えた非常に素晴らしい質量数ふるい法があり、エラドセふるい法とも呼ばれている.2-nを表に入れ、毎回各要素iを最初から遍歴し、iの倍数を表から削除し、最後に残った数は質量数である.
トランスファゲート:質量数をカウント
Count the number of prime numbers less than a non-negative number, n.
非負の整数nより小さいすべての質量数を統計する.

  :

  : 10
  : 4
  :    10        4  ,     2, 3, 5, 7 。

/**
 *
 * Count the number of prime numbers less than a non-negative number, n.
 *            n       。
 *
 */

public class CountPrimes {
    //    （  ）
    public int countPrimes(int n) {
        int result = 0;
        int num = 2;
        while(num <= n){
            int sqrtNum = (int)Math.sqrt(num);
            result++;
            for(int i = 2; i <= sqrtNum; i++){
                if(num % i == 0){
                    result--;
                    break;
                }
            }
            num++;
        }
        return result;
    }

    //      
    // 2-n    ，           i， i        ，          。
    public int countPrimes2(int n){
        boolean[] primeNum = new boolean[n];
        int result = 0;
        for(int i = 2; i < n; i++){
            if(primeNum[i] == false){
                result++;
                for(int times = 2; i * times < n; times++){
                    primeNum[i * times] = true;
                }
            }
        }
        return result;
    }
}

#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう