這個計算素數的計劃能走多遠？

#include <iostream> 

using namespace std; 

int ifprime(long long int); 
int main() 

{ 
    long long int number; 
    cout<<"Enter the number of prime numbers you want to know:\n"; 
    cin>>number; //number is the number of prime numbers to be displayed 
    long long int j=0; 
    long long int m=2;  //m would be used as consecutive natural numbers on which, test of prime number is performed 

    while (1<2) 
    { 
     if(ifprime(m)==1) 
     { 
      j+=1; // j is the counter of the prime numbers found and displayed 
      cout<<m<<endl; 
     } 
     m+=1; 
     if(j==number) 
     { 
      break; 
     } 
    } 

} 

int ifprime(long long int a) 
{ 
    for(int i=2;i<a;i++) 
    { 
     if(a%i==0) 
     { 
      return 0; 
     } 
    } 
    return 1; 
}

的long long int範圍似乎比已知的最大素數要小：/這個計算素數的計劃能走多遠？

即使我計算在long long int範圍內的最後一個素數，我可以計算時間，將採取計算這個數字？

來源

2016-03-01 brainst

只是一個竅門：ifprime應該返回「bool」而不是代表布爾狀態的任意值 – Garf365

提示：通過測試奇數，可以使'ifprime'快一倍。 –

小於2^63-1的最大素數是9223372036854775783.如果您可以每納秒執行一次循環迭代，ifprime將花費近三百年的時間才能找到它。 * unsigned * 64-bit int中最大的素數將需要近六百年的時間。（請注意，在循環中使用'int'是一個錯誤。） – molbdnilo

假設最大的質數是n = 13。然後你的程序會嘗試下面的數字：2, 3, 4,.. 11, 12 所以你必須測試你的數字n - 2次（或多或少n次），直到你達到那一點你的程序必須經過2, 3, 4, ... 11, 12, 13，這也是（更多或更少）n次。 -->複雜度爲O(n^2)。簡單的提示加速您的程序：存儲您在std::vector迄今爲止發現的每個素數，只能嘗試這些。這樣你就避免了整數分解（例如用6（2 * 3）或8（2 * 2 * 2）分割）。

來源

2016-03-01 09:40:21

這個計算素數的計劃能走多遠？

回答

相關問題