如何讓這個非常小的C程序更快？

有沒有簡單的方法可以使這個小程序更快？我已經完成了作業，這是正確的，但太慢了。該程序的目的是打印第n對素數，其中兩個素數之差爲2，給定n。如何讓這個非常小的C程序更快？

#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方面有一些經驗。

來源

2016-09-16 rvvermeulen

'！（A == B）' - >'A！= B'更容易閱讀 – bolov

您的約束是什麼？你可以使用預先計算的素數對數組嗎？一系列加速素數測試的首要素數？ – purplepsycho

它需要多快得到？你是否需要減少算法的大O，或者是否足夠好？ –

這裏是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; 
}

來源

2016-09-16 12:38:51

謝謝！我已經想過取數的平方根，但我認爲只會花費更多的時間。這個替代方案我沒有想到。我嘗試一下，看看它是否足夠。 – rvvermeulen

您只需爲每個數字（不是在每次迭代中）找到'sqrt'一次，但是每次迭代都會執行multiplikation。所以一個有效的整型'sqrt'可能會稍微快一些（取決於優化器可以做什麼）。整數sqrt在這裏討論：http://stackoverflow.com/questions/1100090/looking-for-an-efficient-integer-square-root-algorithm-for-arm-thumb2 –

你往往需要調用isPrime。你寫了

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

...這意味着isPrime被稱爲每個奇數。但是，當您確定例如5是素數，你可以已經知道10,15,20等不會是素數，所以你不需要測試它們。

當使用濾網過濾器時，可以使用這種「交叉」多重素數的方法， Sieve of Eratosthenes algorithm in C實現用於素數爲C的篩選篩選器。

來源

2016-09-16 12:47:30

要找到相差2的素數對，只需找到一個素數，然後加2並測試它是否也是素數。

if (isPrime(x) && isPrime(x+2)) { /* found pair */ }

要找到質數最好的算法是Sieve of Eratosthenes。你需要建立一個高達（N）的查找表，其中N是你可以得到的最大數目。如果一個數字是素數，你可以使用Sieve進入O（1）。在建立Sieve時，你可以建立一個已排序的素數列表。如果你的N很大，你也可以從數P是質數的事實中獲利，因爲它沒有任何質數因子< = SQRT（P）（因爲如果它有一個因子> SQRT（N），那麼它也應該有一個< SQRT（N））。你可以建立一個尺寸爲SQRT（N）的Eratosthenes篩子來獲得一個素數列表，然後測試這些素數是否有任何分歧P.如果沒有分割P，則P是素數。

通過這種方法，您可以測試數量高達10億左右的相對較快且內存很小的數字。

來源

2016-09-16 12:50:37 vz0

避免測試有史以來第三候選素數a, a+2的

對的只可以找到a = 6*n + 5。（對3,5除外）。

爲什麼？

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

因此，而不是測試過其他整數，+ 2，測試與

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

提高循環退出測試

許多處理器/編譯器，計算剩餘時，將也有可用的，用於將近「免費」CPU時間成本的商。因人而異。使用商而不是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; 
}

來源

2016-09-16 14:10:13 chux

如何讓這個非常小的C程序更快？

回答

相關問題