与えられたステップ値を持つ最初の素数ペアを見つけるためのJS関数を書く

Question

**ここではコードワードからの質問です。

素数は規則的に配置されていません。例えば、2~3のステップは1である.3~5のステップは2である.7~11のそれは4である.2~50の間には、以下の2ステップの素数のペアがある。

3,5示した

グラム（整数> = 2）： - 5,7、 - 11、13 - 17、19、 - - 29、31、41、43

我々は、パラメータで機能ステップを記述します我々が探しているステップ、検索（M含む）の開始を与える

メートル（整数> = 2）、

N（intege

上記の例では、（2、2、50）は2と50の間の最初のペアである[3,5]を返します。 2ステップ。

したがって、これらのgステップの素数が存在する場合は、m、nの範囲の間にgのステップで区切られた2つの素数の最初のペアを返します。そうでない場合は、nilまたはnullまたはNoneまたはNothing ）。

例：

ステップ（2、5、7） - > [5,7]又は（5,7）又は{5,7}

ステップ（2、5、5） - >ゼロ又はヌル

ステップ（4、130、200） - ここ> [163、167]及び（163、167）又は{163、167}

は、それが取っている私の溶液 - ですテストに合格するには時間がかかりすぎます。どうすれば効率を上げることができますか？

function step(g, m, n) { 
    var arr = []; 
    function isPrime(num){ 
    for (var k=2; k<num; k++){ 
     if(num%k ===0){ 
     return false; 
     } 
    }return true; 
    } 
    for (var i= m; i < n; i++){ 
    if(isPrime(i)=== true){ 
     arr.push(i); 
    } 
    } 
    var endArr=[]; 
    for(var l=0;l<arr.length;l++) 
    for(var p=1;p<arr.length;p++){ 
    if(arr[l]-arr[l-p]=== g){ 
     endArr.push(arr[l]) 
     endArr.push(arr[l]-g) 
    } 
    } 
    return endArr.slice(0,2).sort(function(a,b){ 
    return a-b; 
}) 

} 

ありがとう！

Answer 1

ここで興味のある点がいくつかあります。

まず、isPrimeの実装は非効率的です。最速の方法は、プリキャストされたセットを使用することです（簡単に作成できます）。ただし、それがなくても、素数で除算するだけで、次の素数がsqrt(cand)より大きくなると脱落します。

たとえば、2,3,5,7が素数であることが既に分かっている場合、11が素数であることを3で除算することで検出できます（5 > Math.sqrt(11)） dは2より大きい偶数をチェックしませんか？

第2に、すべての指定された範囲内の素数を見つけようとし、その後で「差異条件」を満たすすべての素数を見つけようとします。しかし、実際にあなたのタスクは、与えられたステップで2つの素数の最初のペアを見つけることです。

そのことを念頭に置いて、数字（n）をチェックし、それが素数ならばn + gの優劣をチェックしてみてください。そのチェックの結果をキャッシュして、後でスキップすることができます。ここで

---

は一つの可能​​なアプローチがあります：

function findPrimesByStep(g, m, n) { 
    let primes = new Set([2]); 

    function isPrimeNumber(candidate) { 
    if (primes.has(candidate)) { 
     return true; 
    } 

    let lim = Math.sqrt(candidate); 
    for (let prime of primes) { 
     if (prime > lim) { 
     break; 
     } 

     if (candidate % prime === 0) { 
     return false; 
     } 
    } 

    primes.add(candidate); 
    return true; 
    } 

    n = n - g; 
    for (let i = 3; i <= n; i += 2) { 
    let isPrime = isPrimeNumber(i); 
    if (isPrime && i >= m && isPrimeNumber(i + g)) { 
    return [i, i + g]; 
    } 
    } 

    return null; 
} 

これは不完全で、最適化されていないの両方である（それが2をスキップし、些細な例に対してチェックしない、1はsqrt(n)より大きな素数を必要としません）、どのように行うことができるかを示しています。