# 204 Count Primes (有圖)

return、continue、break 差異 / 想好 pattern 再寫 code / 先存值就不會重覆算到 / 複習

LeetCode 這題想了很久...

Count the number of prime numbers less than a non-negative number, n
input: number
output: how many 質數

首先我們來想質數的特性

質數 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29...]

比較笨想法

• [2, 3] 是質數

• > 3 就是每次 + 2 檢查是否除的進

num = 11
用 3 5 7 9 去得餘數是否為零
11%3 != 0
11%5 != 0
11%7 != 0
11%9 != 0
都除不進所以 11 是質數

function isPrime(num){
    if(num == 2 || num == 3){
        return true;
    }
    if(num%2 == 0){
        return false
    }
    let divisor = 3;
    // 這邊比較笨 因為就會 %3 % 5 %7 %9 %11 % 13 %15
    // 而不是 %3 %5 %7 %11 %13 %17
    while(divisor< num){
        if(num%divisor==0){
            return false
        }
        divisor += 2;
    }
    return true
}

一樣的想法取解這題取得質數有幾個

n = 14
3 5 7 9 11 13

// i 9
// j 3 5 7 


// i 11
// j 3 5 7 9

// i 13
// 3 5 7 9 11


// i 15
// j 3 5 7 9 11 13

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;
};

改善

• 其實重覆的值就不用再算一次，例如 15 再 %3 時候就知道不是餘數，所以不用再 %5 算一次

var countPrimes = function(n) {
    if( n<3 ){ return 0; }

    var count = 0;
    var primeMap = new Array(n);
    for( var i=2;i<n;i++){
        if( primeMap[i] ){
            continue;
        }
        count++;
        for(var j=i;j<n;j=j+i){
            primeMap[j] = true;
        }
    }
    return count;
};

學到什麼

這題學挺多的，先是 return、continue、break 差異

Return

function print(nums){
    return "return";
    // 以下不會執行
    for(let i = 0; i< nums; i++){

    }
}

Break

function print(nums){
    for(let i = 0; i< nums; i++){
        
        if(i == 2){
            break
        }
        console.log("i: ", i)
    }
} 
print(10);
// 0 1 2

Continue

function print(nums){
    // 以下不會執行
    for(let i = 0; i< nums; i++){
        
        if(i == 2){
            continue;
        }
        console.log("i: ", i)
    }
} 
print(5);
// 0 1 3 4 5 

再來就是可以先存值就不用重算一次