Discuss / JavaScript / Eratosthenes 法求素数

Eratosthenes 法求素数

Topic source
function get_primes(arr) {
    var isprime = new Array(arr.length);
    for (var i=0; i < isprime.length; ++i) {
        isprime[i] = 0;
    }
    isprime[0] = isprime[1] = 1;
    for (var i=2; i <= arr.length; ++i) {
        if(! isprime[i]){
            for (var j=i+i; j < arr.length; j+=i) {
                isprime[j] = 1;
            }
        }
    }
    return (arr.filter(function(s){
        return isprime[s] == 0;
    }));
}
var x,r,arr = [];
for (var x=1; x < 100; ++x) {
    arr.push(x);
}
r = get_primes(arr);
if(r.toString() === [2,3,5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97].toString()){
    console.log("accept!");
}else{
    console.log("Wrong!");
}

  • 1

Reply