← 都来码 / Dolaima← 例程索引javascript/school/sieve.js 原文

javascript/school/sieve.js · 1124 字节 · 下载原文

// 埃拉托斯特尼筛法 —— 求 2..limit 以内的全部素数
// Sieve of Eratosthenes -- all primes up to `limit`
//
// 来源 / Source: Rosetta Code「Sieve of Eratosthenes」JavaScript 条目(GFDL 1.2 / CC-BY-SA 3.0)
//   https://rosettacode.org/wiki/Sieve_of_Eratosthenes
// 改编 / Adapted: 输出由 print/alert 改为本平台的 println_int。
//   Output changed from print/alert to this platform's println_int.

function eratosthenes(limit) {
    var primes = [];
    if (limit >= 2) {
        var sqrtlmt = Math.sqrt(limit) - 2;
        var nums = new Array();
        for (var i = 2; i <= limit; i++)
            nums.push(i);
        for (var i = 0; i <= sqrtlmt; i++) {
            var p = nums[i];
            if (p)
                for (var j = p * p - 2; j < nums.length; j += p)
                    nums[j] = 0;
        }
        for (var i = 0; i < nums.length; i++) {
            var p = nums[i];
            if (p)
                primes.push(p);
        }
    }
    return primes;
}

var primes = eratosthenes(100);

for (var i = 0; i < primes.length; i++) {
    println_int(primes[i]);
}