プライム・シーブの非効率性はどこでですか？

Question

私はコースを取っており、プライム・シーブを作る必要がありました。私のインストラクターのコードは、私の2倍の速さで実行されています。あなたは私が改善できるものについていくつかの洞察を与えることができますか？

var primeSieve = function (end) { 
    var results = []; 

    for(var i = 0; i <= end; i++) { 
    results.push(i); 
    } 

    results[0] = null; 
    results[1] = null; 

    for(var i = 2; i <= end;) { 
    var j = i + i; 

    do { 
     results[j] = null; 
     j = j + i; 
    } while (j <= end); 

    do { 
     i++; 
    } while(results[i] !== null); 
    } 

    return results.filter((val) => val); 
}; 

Answer 1

最初の数値はi * iで、i + iではないため、すべての下位の倍数はすでに別のプライムによってヌルに設定されているためです。 i = 7 2 * 7（すでにヌルに2に設定）、3 * 7（3で）、4 * 7（ヌルで2に設定）... ただし、 nullは7 * 7

また、ループは「終了」まで続きますが、最初に外すことができるのはi * iです。i> sqrt（end）のすべての繰り返しは何も行いません。

この投稿は、これらとさらなる改善と実装を持っている：//codereview.stackexchange：すでにあなたのコードを考慮Most elegant way to generate prime numbers