用c++找出质数最快的算法是什么?我已经使用了sieve的算法,但我仍然希望它更快!
当前回答
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
其他回答
另一个Python实现比死亡面具推销员的答案更直接,也更快:
import numpy as np
def prime_numbers(limit: int) -> list[int]:
"""Provide a list of all prime numbers <= the limit."""
is_prime = np.full((limit + 1, ), True)
is_prime[0:2] = False
for n in range(2, limit + 1):
if is_prime[n]:
is_prime[n**2::n] = False
return list(np.where(is_prime)[0])
你可以进一步优化,例如,排除2,或者硬编码更多质数,但我想保持简单。
*示例运行时比较(注意:我使用了其他实现的优化形式,见我的评论):
一个非常快速的Atkin Sieve的实现是Dan Bernstein的primegen。这个筛子比埃拉托色尼的筛子更有效率。他的页面有一些基准测试信息。
#include <iostream>
using namespace std;
int set [1000000];
int main (){
for (int i=0; i<1000000; i++){
set [i] = 0;
}
int set_size= 1000;
set [set_size];
set [0] = 2;
set [1] = 3;
int Ps = 0;
int last = 2;
cout << 2 << " " << 3 << " ";
for (int n=1; n<10000; n++){
int t = 0;
Ps = (n%2)+1+(3*n);
for (int i=0; i==i; i++){
if (set [i] == 0) break;
if (Ps%set[i]==0){
t=1;
break;
}
}
if (t==0){
cout << Ps << " ";
set [last] = Ps;
last++;
}
}
//cout << last << endl;
cout << endl;
system ("pause");
return 0;
}
#include<iostream>
using namespace std;
void main()
{
int num,i,j,prime;
cout<<"Enter the upper limit :";
cin>>num;
cout<<"Prime numbers till "<<num<<" are :2, ";
for(i=3;i<=num;i++)
{
prime=1;
for(j=2;j<i;j++)
{
if(i%j==0)
{
prime=0;
break;
}
}
if(prime==1)
cout<<i<<", ";
}
}
如果它必须非常快,你可以包括一个质数列表: http://www.bigprimes.net/archive/prime/
如果你只想知道某个数是不是质数,维基百科上列出了各种质数判别法。它们可能是确定大数是否为质数的最快方法,特别是因为它们可以告诉你一个数是否为质数。