Poj 2689 Prime Distance ----大区间素数筛选

Sol：筛选素数就可以了。。。。（模版题）

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 100000 + 10; const int maxm = 1000000 + 10; int prime[maxn+1]; void getprime() { memset(prime,0,sizeof(prime)); for(int i=2;i<=maxn;i++) { if(!prime[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0]&&prime[j]<=maxn/i;j++) { prime[prime[j]*i]=1; if(i%prime[j]==0) break; } } } bool notprime[maxm]; int prime2[maxm]; void getprime2(int L,int R) { memset(notprime,false,sizeof(notprime)); if(L<2) L=2; for(int i=1;i<=prime[0]&&(long long)prime[i]*prime[i]<=R;i++) { int s=L/prime[i]+(L%prime[i]>0); if(s==1) s=2; for(int j=s;(long long)j*prime[i]<=R;j++) if((long long)j*prime[i]>=L) notprime[j*prime[i]-L]=true; } prime2[0]=0; for(int i=0;i<=R-L;i++) if(!notprime[i]) prime2[++prime2[0]]=i+L; } int main() { getprime(); int L,U; while(~scanf("%d%d",&L,&U)) { getprime2(L,U); if(prime2[0]<2) printf("There are no adjacent primes.\n"); else { int x1=0,x2=100000000,y1=0,y2=0; for(int i=1;i
      
       y2-y1) { y1=prime2[i]; y2=prime2[i+1]; } } printf("%d,%d are closest, %d,%d are most distant.\n",x1,x2,y1,y2); } } return 0; }