这个计算素数的计划能走多远？

#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

这个计算素数的计划能走多远？

回答

相关问题