LOG

素数の数え上げ

let setPrimes = (num)=>{
    let arr = [2];
    for(let n = 3; n <= num; n += 2){ // 2以外で偶数が素数にはなり得ないの i+=2
        let threshold = Math.floor(Math.sqrt(n)); // 閾値 √n
        let isPrime   = true;
        // 素数かどうか確認
        // arrに入っている素数で割り切れなければ素数
        for(let i = 1, l = arr.length; i < l; i++){
            let prime = arr[i];
            // √35が5.916であることから
            // 1~5の数 * n = 35である。
            // またn * m = aの時に、a % m = 0であれば、 a % n = 0である。
            // このことから余りを求める範囲はthreshold以下で良いということがわかる。
            if(prime > threshold) break;
            if(n % prime === 0){
                isPrime = false;
                break;
            }
        }
        if(isPrime) arr.push(n);
    }
    return arr;
}
let primeArr = setPrimes(100);
console.log(primeArr);