0 
var fs = require('fs');
var outfile = "primes.txt";
function getPrimes(max) {
    var primeSieve = [], i, j, primes = [];
    for (i = 2; i <= max; ++i) {
        if (!primeSieve[i]) {
            // i has not been marked - it is prime
            primes.push(i);
            for (j = i << 1; j <= max; j += i) {
                primeSieve[j] = true;
            }
        }
    }
    return primes;
}
fs.writeFileSync(outfile,  getPrimes(1000).slice(0,100) + ",");
console.log("Script: " + __filename + "\nWrote: " + getPrimes(1000).slice(0,100) + "To: " + outfile);

出力を生成するために変更した上記のコードがあります (他の誰かによって提供されたメイン アルゴリズム)。私はJavascriptを初めて使用し、次の行が実際に何をしているのか、および << 演算子が何を意味するのかわかりません(Javascript Webサイトで見つけることができませんでした)。

for (j = i << 1; j <= max; j += i)

メインのprimeSieve配列の関連する数値をtrueとしてマークしているため、素数配列にデータが入力されないことはわかっていますが、これがどのように行われているかはわかりません。

4

1 に答える 1

1

<<演算子は左シフト演算子です。左の引数 (必要に応じて整数値に変換した後) は、右の引数で指定されたビット数だけ左にシフトされ、右にゼロが埋められます。左に 1 シフトすることは、2 を掛けることと同じです。

内側のループは、 の倍数であるインデックスにあるtrueのすべての要素に格納するだけです。したがって、 が である場合、は以前のものの倍数でなければなりません(したがって、素数にはなりません)。逆に、が でない場合、 の以前の値の倍数ではありませんでした。から までのすべての整数が含まれているため、素数でなければなりません。primeSieveiprimeSieve[j]truejijprimeSieve[i]truei2i-1i

すべての素数を特定の最大値まで収集する場合、この方法は、各整数の素数を個別にテストする手法よりもはるかに優れています。ただし、これは最も効率的な方法とはほど遠いものです。たとえば、 の要素が複数回primeSieve設定される可能性があることに注意してください。trueたとえば、は の場合との場合にprimeSieve[6]設定されます。また、の平方根を一度超えると、 までのすべての合成数がその時点でマークされていることが保証されるため、内側のループは無駄になります。これがどのように機能するか、およびさらに効率的な方法へのポインタの詳細については、エラトステネスのふるいに関するウィキペディアの記事を参照してください。i==2i==3imaxmax

PS そのコードは怪しいほど見覚えがあります。:-)

于 2013-06-23T02:24:38.693 に答える