Day 22 - LeetCode 204. Count Primes

LeetCode 204. Count Primes

題目

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

翻譯

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

想法

判斷n之下有幾個質數, 跑回圈去除就可以
質數p的定義就是 p/2, p/3 ....p/(p-1) 都不等於0,
實作可以跳過2的倍數

詳細參閱

https://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

質數wiki:
https://zh.wikipedia.org/wiki/%E7%B4%A0%E6%95%B0

---

Code

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

    let count = 1;
    //跳過2的倍數, 偶數不會是質數, 自己是質數的話不計算
    for ( let i = 3; i < n; i+= 2 ) {
        //只要除到平方根
        for ( let j = 3; j * j <= i; j += 2 ) {
            //被比自己小的數除盡, 代表不是質數
            if ( i % j == 0 ) {
                count --;
                break;
            }
        }
        count++;
    }
    return count;
};

Run