前N個素數優化

我已經看到了一些與論證有關的問題，但只要沒有人完全匹配我要求的內容，我正在做一個新的。我必須計算前N個素數（在這個例子中爲1000）。我推出了一種工作正常的算法，但它並沒有得到優化。前N個素數優化

#include<stdio.h> 
#define MAX_NUMBERS 1000 
int main() 
{ 
    int prime[MAX_NUMBERS]={0}; 
    int filled=0; 
    prime[filled++]=2; 
    int n=0,i=0; 
    while(filled<MAX_NUMBERS) { 
     for(n=prime[filled-1]+1; ;n++) { 
     int found =0; 
     for(i=0; i<filled && (found==0); i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
      } 
     } 
     if(!found) { 
      break; 
     } 
     } 
     /* we know that this always exists */ 
     prime[filled++]=n; 
    } 
    for(i=0;i<filled;i++) { 
     printf("prime number %d\n", prime[i]); 
    } 
    return 0;

}

不要一個人有一個想法如何可以優化？在這種情況下是否有任何算法變更可以提供幫助？

來源

2013-11-27 user3026136

「優化」是什麼意思？ –

是否需要優化？性能目前是一個問題嗎？ –

也許這將是[代碼評論]（http://codereview.stackexchange.com/）的好選擇，因爲代碼目前正在工作。 – Geobits

如果您需要減少執行的循環次數，可以將小素數表存儲在源代碼中。

另一個小的優化是基於大於3的素數都是形式6k-1或6k + 1的事實。因此，不要每六個檢查三個奇數，只要檢查兩個素數。

但更好的方法來發現的素數是使用某種篩子上面提到的： Sieve of Eratosthenes，Sieve of Atkin，Sieve of Sundaram。

來源

2013-11-27 19:26:51 ile

您可以通過執行

for(i = 0; prime[i] <= sqrt(n); i++) {...}

我用sqrt(filled)因爲你並不需要檢查比它的平方更大一些知道它是否是除盡了不到它降低你的圈數（不包括1）。（不要忘了包括`頭）

來源

2013-11-27 18:03:57 haccks

@CareyGregory循環用於遍歷素數組，而不是從1到sqrt（填充）的數字。 –

Doh！粗心評論被刪除。 –

雖然我更喜歡我*我對sqrt函數，並有一個小錯字，素[我] *素[我]

int found =0; 
     for(i=0; i<filled && (found==0); i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
      } 
     } 
     if(!found) { 
      break; 
     }

更改爲：

int found =0; 
     for(i=0; i < filled && prime[i]*prime[i]<=n; i++) { 
      if((n%prime[i]) == 0) { 
       found = 1; 
       break; 
      } 
     } 
     if(!found) { 
      break; 
     }

來源

2013-11-27 18:10:15

@VikramBhat你是對的。應該有=。 –

這樣更好（你注意到你發現了9或25？） – wildplasser

終於找到了！ –

做的最好的辦法就是通過像下面是最容易和非常有效的篩分方法： -

Sieve of eratosthenes

來源

2013-11-27 18:27:38

不是已有的算法已經在使用篩子嗎？ –

@AbhishekBansal篩子比他所做的更有效率，首先它將每個數字都視爲素數，並且在每次迭代中將所有素數的倍數細化。只需向他提及如何有效完成我給出的鏈接。 –

也[atkin的篩]（http://en.wikipedia.org/wiki/Sieve_of_Atkin）略快（儘管對於op的目的來說微不足道） – ile

前N個素數優化

回答

相關問題