エラトステネスのセグメント化された篩をJavaScriptで実装する

Question

最近、本当に大きな数値のエラトステネのセグメント化された篩の高速実装について読んだ。続き

は同じの実装です：

function sieve(low, high) { 

    var primeArray = [], ll = Math.sqrt(low), output = []; 

    for (var i = 0; i < high; i++) { 
     primeArray[i] = true; 
    } 

    for (var i = 2; i <= ll; i++) { 
     if (primeArray[i]) { 
      for (var j = i * i; j < high; j += i) { 
       primeArray[j] = false; 
      } 
     } 
    } 

    for (var i = 2; i < ll; i++) { 
     if(primeArray[i]) 
     { 
      var segmentStart = Math.floor(low/i) * i; 

      for(var j = segmentStart; j <= high; j+=i) 
      { 
       primeArray[j] = false; 
      } 
     } 
    } 

    for(var i = low; i <= high; i++) 
    { 
     if(primeArray[i]) 
     { 
      output.push(i); 
     } 
    } 

    return output; 
}; 

私はそれが間違って持っている場所を見つけ出すように見えることはできません。 おそらくそれはあまりにも長い間働いています。例えば

：

sieve(4,10)[5,7] を返す必要があります。しかし、それはあなたが十分に高い要因をチェックされていない[5,7,9]

Answer 1

を返しています。その理由は、平方根の限界が間違っているためです。変更：

ll = Math.sqrt(low) 

ll = Math.sqrt(high) 

への最初のループなければならないも含めて highにループ、最後に出力ループは同じことをするので。同じ理由で、3番目の外側ループも llにループする必要があります。

セグメントの開始点を計算する部分は、最初の繰り返しで素数を消してはいけません。あなたは、セグメンテーション部にceil代わりのfloorを使用することができます

  if (primeArray[segmentStart]) segmentStart += i; 

注：lowが低いとき1.だから、これを追加するようにこれは一般的に、発生します。

修正されたコードは次のようになります。

function sieve(low, high) { 
 
    var primeArray = [], ll = Math.sqrt(high), output = []; 
 

 
    for (var i = 2; i <= high; i++) { 
 
     primeArray[i] = true; 
 
    } 
 

 
    for (var i = 2; i <= ll; i++) { 
 
     if (primeArray[i]) { 
 
      for (var j = i * i; j <= high; j += i) { 
 
       primeArray[j] = false; 
 
      } 
 
     } 
 
    } 
 

 
    for (var i = 2; i <= ll; i++) { 
 
     if(primeArray[i]) { 
 
      var segmentStart = Math.ceil(low/i) * i; 
 
      // need this test to ensure we are not deleting primes 
 
      if (primeArray[segmentStart]) segmentStart += i; 
 

 
      for(var j = segmentStart; j <= high; j+=i) { 
 
       primeArray[j] = false; 
 
      } 
 
     } 
 
    } 
 

 
    for(var i = low; i <= high; i++) { 
 
     if(primeArray[i]) { 
 
      output.push(i); 
 
     } 
 
    } 
 
    return output; 
 
} 
 

 
console.log(sieve(1, 20));