POJ 3518 Prime Gap(素数)

id=3518

题意：

       给你一个数。假设该数是素数就输出0. 否则输出比这个数大的素数与比这个数小的素数的差值。

分析：

       明显本题先要用筛选法求出130W(严格的话应该是求第100001个素数)以内的全部素数。

       然后推断给的数是否是素数就可以。

       假设不是素数。那么就找出它在素数素组内的上界和下界，输出两个素数的差值就可以。

       筛选法求素数可见：

      

AC代码：

#include
     
      #include
      
       #include
       
        using namespace std;const int maxn=1300000;int prime[maxn+5];int get_prime(){    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;        }    }    return prime[0];}int main(){    //生成maxn内的全部素数    get_prime();    int x;    while(scanf("%d",&x)==1 && x)    {        int bound=lower_bound(prime+1,prime+prime[0]+1,x)-prime;        if(prime[bound]==x) printf("0\n");        else printf("%d\n",prime[bound]-prime[bound-1]);    }    return 0;}