この非常に小さなCプログラムをもっと速くするにはどうすればいいですか？

Question

この小さなプログラムをより速くする簡単な方法はありますか？私は割り当てのためにそれを作った、そしてそれは正しいが、遅すぎる。プログラムの目的は、nの2つの素数のペアを印刷することです。

#include <stdio.h> 
#include <stdlib.h> 
#include <stdbool.h> 

bool isPrime(int number) { 
    for (int i = 3; i <= number/2; i += 2) { 
    if (!(number%i)) { 
     return 0; 
    } 
    } 

    return 1; 
} 

int findNumber(int n) { 
    int prevPrime, currentNumber = 3; 

    for (int i = 0; i < n; i++) { 
    do { 
     prevPrime = currentNumber; 

     do {        
     currentNumber+=2; 
     } while (!isPrime(currentNumber)); 

    } while (!(currentNumber - 2 == prevPrime)); 
    } 

    return currentNumber; 
} 

int main(int argc, char *argv[]) { 
    int numberin, numberout; 
    scanf ("%d", &numberin); 

    numberout = findNumber(numberin); 

    printf("%d %d\n", numberout - 2, numberout); 
    return 0; 
} 

は、私は現在の数まで検出されたすべての素数を含んでいて、代わりにすべての数字のリストで各番号を分けるだろう配列またはリストのいくつかの種類を使用して考えられているが、私たちは本当にこれらの異なるデータ構造をカバーしていませんまだ私はこの問題を解決することができなくてはならないと感じています。私はちょうどCで始まっていますが、私はPythonとJavaでいくつかの経験があります。ここで

Answer 1

はisPrimeでループをスピードアップするために改良したものである：

bool isPrime(int number) { 
    for (int i = 3; i * i <= number; i += 2) { // Changed the loop condition 
    if (!(number%i)) { 
     return 0; 
    } 
    } 

    return 1; 
} 

Answer 2

あなたはより頻繁に必要以上isPrimeを呼んでいます。あなたはisPrimeは、すべての奇数のために呼ばれていることを意味している...

currentNummber = 3; 
/* ... */ 
do {        
    currentNumber+=2; 
} while (!isPrime(currentNumber)); 

を書きました。しかし、あなたがそれを特定したときなど。 5が素数であれば、すでに10,15,20などが素数にならないことを伝えることができるので、それらをテストする必要はありません。

この「クロスアウト」の素数のアプローチは、ふるいフィルターを使用するときに行われます。 Sieve of Eratosthenes algorithm in C Cの素数の篩フィルタの実装について

Answer 3

2で異なる素数のペアを見つけるには、素数1つを見つけて2を加え、それが素数であるかどうかを調べるだけでよい。

最良のアルゴリズムはSieve of Eratosthenesです。ルックアップテーブルを（N）まで作成する必要があります.Nは取得できる最大数です。数字が素数の場合は、Sieveを使用してO（1）に入ります。 Sieveを構築する際に、ソートされた素数のリストを作成することができます。

Nが大きい場合は、素数が0以外の場合は、Pが素数であることから利益を得ることができます< = SQRT（P）（SQRT（N）>それはまた1つの< SQRT（N）を持つべきです）。素数のリストを取得するためにサイズSQRT（N）のEratosthenesのSieveを構築し、それらの素数Pのいずれかが存在するかどうかをテストすることができます。Pを割り切れない場合、Pは素数です。

この方法を使用すると、最大10億回ほどの速さで、メモリをほとんど使わずにテストすることができます。

Answer 4

避けテスト史上3番目の候補の素数a, a+2の

ペアのみa = 6*n + 5を見つけることができます。 （ペア3,5を除く）。

なぜですか？

a = 5; 
loop { 
    if (isPrime(a) && isPrime(a+2)) PairCount++; 
    a += 6; 
} 

---

改善ループ終了検査と+ 2、テストと

a + 0 = 6*n + 5 Maybe a prime 
a + 2 = 6*n + 7 Maybe a prime 
a + 4 = 6*n + 9 Not a prime when more than 3 as 6*n + 9 is a multiple of 3 

そうではなく、テストこれまでの他の整数

剰余を計算するとき多くのプロセッサ/コンパイラは、意志ほぼ「フリー」なCPU時間コストである商を使用することもできます。 YMMV。テストループを制限するには、i <= number/2またはi*i <= numberではなく商を使用してください。

sqrt()の使用には、double対intの範囲の正確性、整数への変換、または整数からの変換という多くの問題があります。この作業にはsqrt()を避けることをお勧めします。

追加範囲はunsignedです。

bool isPrime(unsigned x) { 
    // With OP's selective use, the following line is not needed. 
    // Yet needed for a general purpose `isPrime()` 
    if (x%2 == 0) return x == 2; 

    if (x <= 3) return x == 3; 
    unsigned p = 1; 
    unsigned quotient, remainder; 
    do { 
    p += 2; 
    remainder = x%p; 
    if (remainder == 0) return false; 
    quotient = x/p;   // quotient for "free" 
    } while (p < quotient); // Low cost compare 
    return true; 
}