エラトステネスの篩

ソースコード

function primesvalue(n){
    // サイズnのブーリアン値trueを持つリストを作成
    let cache = [];
    for(let i = 0; i < n; i++) {
        cache.push(true);
    }

    // ステップを√n回繰り返します。
    for (let currentPrime = 2; currentPrime < Math.ceil(Math.sqrt(n)); currentPrime++){
        if (!cache[currentPrime]) continue;
        let i = 2;
        let ip = i * currentPrime;
        while (ip < n){
            cache[ip] = false;
            // i*pをアップデートします。
            i += 1;
            ip = i * currentPrime;
        }
    }

    // 素数
    let numbers = [];
    for (let i = 2; i < cache.length; i++){
        if (cache[i]){
            numbers.push(i);
        }
    }

    return numbers;
}