エラトステネスの篩はJavascriptで？

Question

ので、私はJavascriptにWikipediaからこの擬似コードを変換しようとしていた。

Input: an integer n > 1 

Let A be an array of Boolean values, indexed by integers 2 to n, 
initially all set to true. 

for i = 2, 3, 4, ..., not exceeding √n: 
    if A[i] is true: 
    for j = i^2, i^2+i, i^2+2i, i^2+3i, ..., not exceeding n : 
     A[j] := false 

Output: all i such that A[i] is true. 

そして、これは限り私が得たようである：

function getPrimes(num) { 
    var a = []; 
    for (i=2;i<=num;i++){a.push(true);} 
    for (i=2;i<=Math.sqrt(num);i++){ 
    for (var j=i*i, coef=0, l=i;j<num-2;coef++){ 
     j = i*i+coef*l-2; 
     a[j]=false; 
    } 
    for (i=0;i<a.length;i++){ 
     if (a[i]){a.splice(i,1,i+2);} 
    } 
    } 
    return a; 
} 

getPrimes(10); // returns [2, 3, false, 5, false, 7, false, 9, false] 
       // 9 should be false 

あなたが見ることができるように、アルゴリズムはすべてキャッチされていません非素数です。何が私が逃したアイデア？彼らに手を差し伸べたい人には、事前に感謝します。

Answer 1

外部ループの変数iを上書きし、2番目の内部ループにはiも使用します。したがって、外側のループは1回だけ実行されます。

kのように、内側のループに別の変数を使用すると、良い結果が得られます。

しかし、その特定の内側ループをそこに配置する必要はありません。それは本当に一度だけ、戻ってくる直前に実行する必要があります。だからあなたはそれをメインループの外に出すことができます。

ごくわずかな問題は、jがループの本体で増分されるため、最初の内側ループが大きくなり過ぎており、に値を割り当てた後にのみjのテストが行​​われることです。 JavaScriptはその時点でその要素を作成し、配列を長くしますが、それが起こらないようにすればより良いでしょう。

数字0と1を表すために配列aの最初の2つのインデックスを予約しますコードを読みやすくしてください。+2と-2はもう必要ありません。

function getPrimes(num) { 
 
    var a = [...Array(num+1).keys()]; // =[0,1,...,num] 
 
    a[1] = 0; // 1 is not prime 
 
    var rt = Math.sqrt(num); // calculate only once 
 
    for (i=2;i<=rt;i++){ 
 
    for (var j=i*i; j<=num; j+=i) a[j]=0; 
 
    } 
 
    return a.filter(Number); // kick out the zeroes 
 
} 
 
// run it for 30 
 
var a = getPrimes(30); 
 
// Output 
 
console.log(a);