C程序優化/速度提高

作爲初學者，我編寫了一個程序，用於查找不高於輸入自然數（x）的素數（prime）。該程序工作正常（我認爲），但我想讓它工作得更快（對於更高的數字）。這有可能，如果是的話，如何？C程序優化/速度提高

#include <stdio.h> 

int main() { 
    int x, i, j, flag = 1, prime = 0 ; 

    scanf("%d", &x); 
    for (i = 2; i <= x; i++) { 
     j = 2; 
     while (flag == 1 && j < i/2 + 1) { 
      if (i % j == 0) { 
       flag = 0; 
      } 
      j++; 
     } 
     if (flag == 1) { 
      prime++; 
     } 
     flag = 1; 
    } 
    printf("%d\n", prime); 
    return 0; 
}

來源

2015-10-16 Panagiotis Papantonakis

1：找到一個更好的算法。 2.對於你當前的算法，注意只有一個偶素。 3.對於你當前的算法，請注意，如果你在第一個'sqrt（n）'數字中沒有找到除數，'n'就是質數。 – EOF

製作到目前爲止發現的每個素數的列表或數組。只能測試它們作爲除數。如果'6'是一個除數，如果它已經通過'2'和'3'作爲除數，那麼沒有必要進行測試。 –

查看Eratosthenes的篩子。您可以基於此構建更高效的算法。 –

你的算法做試劃分，這很慢。一個更好的算法是埃拉托色尼的2000歲篩：

function primes(n): 
    sieve := makeArray(2..n, True) 
    for p from 2 to n 
     if sieve[p] 
      output p # prime 
      for i from p*p to n step p 
       sieve[i] := False

我要把它留給你翻譯成C.如果你想知道更多，我虛心推薦文章Programming with Prime Numbers在我的博客。

來源

2015-10-17 01:23:17 user448810

對於我從p + p到n步驟p，我應該從'p + p到n步驟p'嗎？ –

@WeatherVane no。 –

@WillNess是的，我看到......'p + p'由'2'照顧。 'p + p + p'由'3'等來處理。 –

有一個着名的素數定理。它指出

π(n)≈n/ln(n)

但是有一些算法來計算這個函數。跟隨鏈接： PNT

Computing π(x): The Meissel, Lehmer, Lagarias, Miller, Odlyzko method

來源

2015-10-17 02:58:26 user2979190

C程序優化/速度提高

回答

相關問題