LeetCode 204. Count Primes

題目

Description:

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

翻譯

給一個n，計算比n小的質數有幾個。

思路

1. 網路上解質數問題的演算法很多，這邊用比較原始的方法
2. 判斷n之下有幾個質數，只要跑迴圈判斷從2~(n-1)中毎一個數是不是質數就可以
3. 質數p的定義就是 p/2 , p/3 , p/4 .... p/(p-1)都不等於0
4. 實作上不需要除到p-1，只需要除到"p的平方根"就可以，而且可以跳過2的倍數 p/2, p/3 , p/5 , p/7 .....

解題

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // n = 3的時候，才會出現第一個比n小的質數2
    if(n < 3) return 0;

    var count = 1;
    // 加快速度，所以跳過2的倍數
    for(var i = 3 ; i < n ; i+=2){
        var flag = true;
        // 判斷i是不是質數
        for(var j = 3 ; j*j <= i; j+=2){
            if(i%j == 0){
                // i能被比自己小的數除盡，表示i不是質數
                flag = false; 
                break;
            }
        }

        if(flag) count++;
    }

    return count;
};