優化素數代碼？

Question

我寫了這段代碼來顯示1到100之間的素數。唯一的條件是不要使用函數，整個代碼應該是內聯的。我會問是否可以改進（優化）更多？

#include<iostream> 

using namespace std; 

int main() { 

    int i=2,j=2; 

    cout<<"Prime numbers between 1 and 100 are:"<<endl; 
    cout<<"2"<<"\t"; 
    while(i!=100) { 
     for(int j=2;j<i;j++) { 
      if(i%j==0) 
      break; 

      if(j==i-1) 
      cout<<i<<"\t"; 
     } 

     i++; 
    } 

    cout<<endl; 
    system("pause"); 
    return 0; 
} 

Answer 1

您正在檢查從2到100的每個數字。但是由於2是唯一的偶數素數，所以您可以跳過每個偶數2之後的數字。這適用於i和j。因此，在3日開始i和j，並通過2

#include<iostream> 

using namespace std; 

int main() { 
    cout<<"Prime numbers between 1 and 100 are:"<<endl; 
    cout<<"2"<<"\t"; 
    for (int i=3; i<100;i+=2) { 
     // This loop stops either when j*j>i or when i is divisible by j. 
     // The first condition means prime, the second, not prime. 
     int j=3; 
     for(;j*j<=i && i%j!=0; j+=2); // No loop body 

     if (j*j>i) cout << i << "\t"; 
    } 
    cout<<endl; 
    return 0; 
} 

遞增它們除了上面提到的技巧，我已經添加了條件j*j<=i這在邏輯上是完全相同的j<=sqrt(i)。當你可以做一個簡單的乘法運算時，不需要計算平方根。

Answer 2

取決於您希望進行的優化。你的情況儘可能的好，我可以看到，如果你是第一次，第二次優化空間（好吧，關閉 - 只要你聽@Paul，它就會）。如果你改變優先順序，Erastothenes的篩子速度會更快（但會佔用你內存的100個布爾值）。

Answer 3

for(int j=2;j<i;j++){ 

這一個不好。

首先，你只需要檢查j <= sqrt(i)，因爲例如7不會休息12分。

其次，你應該跟蹤以前找到的所有素數;保留它的向量，只做這個循環的內容和對於我寫的條件。

Answer 4

你可以優化你的現有代碼：

• 在while循環，你應該有2步，讓你不測試偶數。
• 在你的循環，當你到達數的平方根要測試

你可以使用不同的方法，你應該停止：

• 篩Erastoses的：http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

在Erastoses的篩上只刪除2,3和5可分割的數字將顯着減少您需要測試素數的次數。

Answer 5

避免使用平方根函數，並將您的除數增加2.還有一些棘手的事情在i循環中將可能的素數增加2倍。內部循環甚至不需要檢查2的整除，因爲沒有偶數甚至會被測試。

int i,j,sq; 
int min; 
for(sq = 2; sq <= 10; sq++) 
{ 
    min = (sq-1)*(sq-1); 
    min = min + (min+1)%2; //skip if it's even, so we always start on odd 
    for(i = min; i < sq*sq; i+=2) 
    { 
    for(j = 3; j <= sq; j+=2) 
    { 
     if (i%j == 0) 
     bad; 
    } 
    } 
} 

請注意，sq循環不會增加時間，因爲它會按比例收縮內部循環。

Answer 6

兩個簡單的優化，你可以這樣做：

cout << 2 << '\t'; 
for (int i = 3; i <= 100; ++i) { 
    for (int j = 3, l = (int)sqrt(i); j <= l; j += 2) { 
     if (i % j == 0) { 
      cout << i << '\t'; 
      break; 
     } 
} 

我做了什麼：

數學：

• 停止時j > sqrt(i)，就沒有必要進一步去比。但請注意，sqrt是一個昂貴的功能;對於你的小樣本（從1到100），它可能（讀取，肯定會）花費你更多的使用它。
• 只檢查奇數;做j += 2，而不是由一個

微優化遞增j之一：

• 使用++i代替i++;後者有一個臨時變量，它存儲了原始值i;前者不。
• 打印'\t'作爲字符而不是字符串"\t"。

（這些微的優化很可能由編譯器自動做出反正，但有在明知對他們沒有傷害。）

Answer 7

如果你只是想在100的素數，有沒有必要寫代碼來計算他們。這可能是一個愚蠢的答案，但它可以有效和簡潔地解決你的問題。

int main() { 
    cout << "Prime numbers are:" << endl << "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97" << endl; 
    return 0; 
} 

Answer 8

最有效的方法是完成Eratosthenes的篩。這是一個增量版本，專門爲生產質量最高爲，逐個（最大可達，因爲121 == 11 * 11）而定製。

printf("2 "); 
int m3=9, m5=25, m7=49, i=3; 
for(; i<100; i+=2) 
{ 
    if(i!=m3 && i!=m5 && i!=m7) printf("%d ", i); 
    else 
    { 
     if(i==m3) m3+=6; 
     if(i==m5) m5+=10; 
     if(i==m7) m7+=14; 
    } 
} 

Answer 9

/*** Return an array of primes from 2 to n. ***/ 
int[] function nPrimes(int n) { 
    int primes[]; //memory allocation may be necessary depending upon language. 
    int p = 0; 
    bool prime; 
    for (int i = 2; i <= n; i++) { 
     prime = true; 
     //use (j <= (int)sqrt(i)) instead of (j < i) for cost savings. 
     for (int j = 2; j <= (int)sqrt(i); j++) { 
      if (i % j == 0) { 
       prime = false; 
       break; 
      } 
     } 
     if (prime) { 
      primes[p++] = i; 
     }  
    } 
    return primes; 
}