3
我想实现一个算法来获得1到很大数目之间的素数列表。我打算使用erasthosthenes筛子。但是为了实现筛选,我们不应该首先创建一个包含那么多数字的布尔数组。这不是很消耗内存吗?有没有其他方法可以做到这一点?找到1到2^128之间的素数
我想实现一个算法来获得1到很大数目之间的素数列表。我打算使用erasthosthenes筛子。但是为了实现筛选,我们不应该首先创建一个包含那么多数字的布尔数组。这不是很消耗内存吗?有没有其他方法可以做到这一点?找到1到2^128之间的素数
尽管你可能永远无法存储2^128,但我使用erasthosthenes筛选器在C++中创建了一个程序,我一次只考虑10^5个元素,从而消除了存储限制。
使用./a.out LEFT1 RIGHT1 LEFT2 RIGHT2 ...... 你可以做同样在python
#include<iostream>
#include<stdlib.h>
using namespace std;
int main(int argc,char ** argv){
int prime[100001];
long long l,r;
if((argc-1)%2!=0) cout<<"Invalid arguments: One limit missing"<<endl;
for(long i=0;i<=100001;++i)
prime[i]=1;
prime[0]=prime[1]=0;
for(long i=2;i*i<=100000;++i){
if(prime[i]==1){
for(long j=i+i;j<=100000;j=j+i)
prime[j]=false;
}
}
int cnt=1;
while(cnt<argc){
l=atol(argv[cnt]);
r=atol(argv[cnt+1]);
cnt=cnt+2;
int f=1;
if(r<=100000){
for(long i=l;i<=r;++i){
if(prime[i]){
cout<<i<<endl;
}
}
cout<<endl;
f=0;
}
if(!f) continue;
bool ans[100000]={true};
long long temp=r;
while(temp>l){
r=min(temp,l+100000);
for(long long i=0;i<100000;++i) ans[i]=true;
for(long long i=2;i*i<=r;++i){
if(prime[i]){
long k=l/i;
k=k*i;
if(k<l) k+=i;
if(k==i) k+=i;
for(;k<=r;k=k+i){
ans[k-l]=false;
}
}
}
for(long i=0;i<r-l+1;++i)
if(ans[i]) cout<<l+i<<endl;
cout<<endl;
l=l+100001;
}
}
}
不,你不必浪费内存。您可以在python2中使用xrange,并在python3中使用范围。此外,我建议使用Atkin的筛子。它好得多 – sshashank124
在Linux上,你可以使用'primes'(通常从Debian的'bsdgames'软件包安装'/ usr/games/primes') –
yes,实现generator并根据需求计算下一个素数 –