python - 查找 1 到 ~2^128 之间的素数

Question

我想实现一个算法来获得一个介于 1 和一个非常大的数之间的素数列表。我打算用 Erasthosthenes 筛子。但是要实现筛子，我们不应该首先创建一个包含这么多数字的布尔数组。这不是很消耗内存吗？有没有其他方法可以做到这一点？

Answer 1

尽管您可能永远无法存储 2^128 ，但我使用 Erasthosthenes sieve 在 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;

    }
    }
}