poj2689Prime Distance 素數篩選

題目要求：在給定范圍L~R中找出差值最大和最小的兩組素數

要在L~R篩選素數 ，直接算出1~2,147,483,647的話肯定超時

但實際上，篩選1~2,147,483,647中的素數需要的因子並不多，只要找出2~sqrt(2,147,483,647)中的素數就夠了，篩選法就是這麼干的

之後用這些素數對L~R的區間試除 得到L~R內的素數 求出結果

[cpp]
#include<iostream>  
#include<cstdio>  
#include<cstring>  
using namespace std; 
 
bool Q[1001000]; 
bool p[50000]; 
int P[5000]; 
 
int main() 
{ 
    __int64 i,j,k,L,R; 
    for(i=2;i<=50000;i+=2)   p[i]=0,p[i+1]=1;    p[1]=0;p[2]=1;P[1]=2;P[0]=1; 
    for(i=1;i<=46345;i+=2) 
    { 
        if(p[i]) 
        { 
            int k=i*i; 
            while(k<50000){ 
                p[k]=0; 
                k+=2*i; 
            } 
            P[++P[0]]=i; 
        } 
    } 
     
    while(scanf("%I64d%I64d",&L,&R)!=EOF) 
    { 
         
        int Start; 
        for(i=L;i<=R;i++)    Q[i-L]=1; 
        for(i=1;i<=P[0];i++) 
        {    
            if(P[i]>=R)  break; 
            Start=L/P[i]; 
            if(Start*P[i]<L) Start++; 
            if(Start==1)    Start++; 
            for(j=Start;j*P[i]<=R;j++)           Q[j*P[i]-L]=0; 
        } 
        if(L==1)    Q[0]=0,Q[2]=1; 
        if(L==2)    Q[0]=1; 
        __int64 pre=R,now=0,min=1000000000,max=0,a,b,x,y; 
        for(i=L;i<=R;i++){ 
            if(Q[i-L]){ 
                pre=i; 
                break; 
            } 
        } 
        for(i=pre+1;i<=R;i++) 
        { 
            if(Q[i-L]){ 
                now=i; 
                if(now-pre<min){ 
                    min=now-pre; 
                    a=pre,b=now; 
                } 
                if(now-pre>max){ 
                    max=now-pre; 
                    x=pre,y=now; 
                } 
                pre=now; 
            } 
        } 
        if(!now)    printf("There are no adjacent primes.\n"); 
        else    printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a,b,x,y); 
    } 
    return 0; 
} 
/*
 
2000000000 2000000001
2146483648 2147483647
 
*/ 
         

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

bool Q[1001000];
bool p[50000];
int P[5000];

int main()
{
 __int64 i,j,k,L,R;
 for(i=2;i<=50000;i+=2) p[i]=0,p[i+1]=1; p[1]=0;p[2]=1;P[1]=2;P[0]=1;
 for(i=1;i<=46345;i+=2)
 {
  if(p[i])
  {
   int k=i*i;
   while(k<50000){
    p[k]=0;
    k+=2*i;
   }
   P[++P[0]]=i;
  }
 }
 
 while(scanf("%I64d%I64d",&L,&R)!=EOF)
 {
  
  int Start;
  for(i=L;i<=R;i++) Q[i-L]=1;
  for(i=1;i<=P[0];i++)
  { 
   if(P[i]>=R) break;
   Start=L/P[i];
   if(Start*P[i]<L) Start++;
   if(Start==1) Start++;
   for(j=Start;j*P[i]<=R;j++)   Q[j*P[i]-L]=0;
  }
  if(L==1) Q[0]=0,Q[2]=1;
  if(L==2) Q[0]=1;
  __int64 pre=R,now=0,min=1000000000,max=0,a,b,x,y;
  for(i=L;i<=R;i++){
   if(Q[i-L]){
    pre=i;
    break;
   }
  }
  for(i=pre+1;i<=R;i++)
  {
   if(Q[i-L]){
    now=i;
    if(now-pre<min){
     min=now-pre;
     a=pre,b=now;
    }
    if(now-pre>max){
     max=now-pre;
     x=pre,y=now;
    }
    pre=now;
   }
  }
  if(!now) printf("There are no adjacent primes.\n");
  else printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",a,b,x,y);
 }
 return 0;
}
/*

2000000000 2000000001
2146483648 2147483647

*/