1과 ~ 2 사이의 소수 찾기^128

Question

1과 매우 큰 숫자 사이의 소수 목록을 얻기위한 알고리즘을 구현하고 싶습니다. 나는 erasthosthenes 체를 사용하려고했다. 그러나 체를 구현하려면 먼저 많은 수의 불린 배열을 만들어서는 안됩니다. 그다지 메모리를 소비하지 않습니까? 이 작업을 수행 할 수있는 대안이 있습니까?

Answer 1

2^128을 저장할 수는 없지만 한 번에 10^5 개 요소 만 고려한 erasthosthenes sieve를 사용하여 C++로 프로그램을 작성하여 저장 제한을 없앴습니다.

사용 ./a.out Left 1 RIGHT1 left2 Right 2 ... 당신은 파이썬에서 동일한 작업을 수행 할 수

#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; 

    } 
    } 
}