素数を見つけるためのJavaScriptコードの最適化

Question

私はcodewars.comのチャレンジを試みていますが、私のコードをより効率的にするためのいくつかの問題があります。チャレンジの指示は、範囲内のすべての素数を見つけることです。そして、それらの間に指定された隙間を持つ2つの素数を見つけなければなりません。

動作するアルゴリズムを作成しましたが、すべてのテストケースを完了するのには時間がかかります。あなたは以下のコードを見ることができます：

function gap(g, m, n) { 
// your code 

var stopNumber; 
var checkIfInteger; 
var primeNumbersInRange = []; 
var arrayIndex = 0; 
var gap; 

//iterate through all of the numbers in the range and find if they're prime 
for(var numberToCheck = m; numberToCheck <= n; numberToCheck++){ 

     var checkedTwoAndThreePass = true; 

     checkIfInteger = numberToCheck/2; 

     if(Number.isInteger(checkIfInteger)){ 
     checkedTwoAndThreePass = false; 
     } 

     checkIfInteger = numberToCheck/3; 

     if(Number.isInteger(checkIfInteger)){ 
     checkedTwoAndThreePass = false; 
     } 

     if(checkedTwoAndThreePass){ 

     var k = 1; 
     var primeNumberCheck = true; 

     stopNumber = Math.sqrt(numberToCheck); 

     while(((6 * k) - 1) <= stopNumber & primeNumberCheck === true){ 

      checkIfInteger = numberToCheck/((6 * k) - 1); 

      if(Number.isInteger(checkIfInteger)){ 
      primeNumberCheck = false; 
      }  
      else{ 

      checkIfInteger = numberToCheck/((6 * k) + 1); 

      if(Number.isInteger(checkIfInteger)){ 
       primeNumberCheck = false; 
      } 
      } 
      k++; 
     } 

     if(primeNumberCheck === true){ 
      primeNumbersInRange[arrayIndex] = numberToCheck; 
      arrayIndex++; 
     } 

     } 

} 

for(var i = 0; i < primeNumbersInRange.length; i++){ 
    gap = primeNumbersInRange[(i+1)] - primeNumbersInRange[i]; 
    if(gap === g){ 
    var primeNumbersThatMeetGap = [primeNumbersInRange[i], primeNumbersInRange[(i+1)]]; 
    return primeNumbersThatMeetGap; 
    } 
} 
var primeNumbersThatMeetGap = null; 
return primeNumbersThatMeetGap; 
} 

Answer 1

可能な方法の1つは、Sieve of Eratosthenesアルゴリズムを実装することです。 Example implementation here。

しかし、それだけでは十分ではありません。あなたはへの道を見つける必要がありますあなた自身のすべての時間を繰り返すか、または必要なものだけを検索してください問題の。

Answer 2

私はこの仕事を、通常はEratosthenesの篩よりも遅いと思われるSieve of Sundaramを使用して実装しましたが、少し最適化すると、実装されたEratosthenesの篩の最も速い実装より約2倍速いことが判明しましたその質問の下で。最初の1M数で78498個の素数を見つけることは25ミリ秒以下でした。

これは正常に動作しています。in this answer

現在、私はこのアルゴリズムのセグメント化バージョンを作成しています。

1. シングルコアの10^9ではるかに高速な応答です。
2. ワーカーを使用して、使用可能な空きスレッドよりも大きなジョブを生成することができます。

私はコードを確定したら、私はそのトピックの私の既存の答えの下の補足として、それを参加します。