题目链接

http://poj.org/problem?id=2689

解题思路

前置知识：任何一个合数n都至少有一个质因子小于等于根号n；
因为l和r的范围是1 ~ 2^31，范围太大，显然不能算出1 ~ 2^31的素数再枚举，但是发现r与l的差很小，1e6。
我们的大致思路：
标记l ~ r区间内的合数，未被标记的就是质数，我们再枚举质数之间的差值的大小并记录，输出。
难点是如何标记l ~ r区间内的合数，
假设i是l ~ r区间内的合数，则有i的一个质因子pi在2 ~ 根号i之间，i最大可能取r，所以l ~ r区间内任意一个合数的一个质因子一定在2 ~ 根号r之间。那么对于r最大为2147483647，那么我们就统计1 ~ 根号2147483647区间内的质数。
对于2 ~ 根号r之间的所有质数p，把l ~ r区间内能被p整除的数标记下来，这些就是l ~ r区间内的合数，即标记i * p ( ceil(l/p) <= i <= floor(r/p) )
未被标记的为质数，对相邻的质数两两比较，找出差值最大的即可。

细节实现在代码中有注释

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#define ll long long

using namespace std;
const int N=1e6+100;

int mx,mn,l,r,mxl,mxr,mnl,mnr,cnt,cntp;
bool vis[N];
int p[50010];
ll prime[50010]; 

void Prime()//欧拉筛 
{
    memset(vis,0,sizeof vis);
    for(int i=2;i<=50000;i++) 
    {
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt;j++)
        {
            if(i*prime[j]>50000) break;
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

int main()
{
    Prime();
    while(cin>>l>>r)
    {
        mn=2147483647,mx=0; cntp=0;
        memset(vis,0,sizeof vis);
        if(l==1) vis[0]=1;//特判一下，如果l=1，那么在收集l~r之间的素数时，因为l=1，vis[1-l]=0，！vis=1，所以1也会被算作素数 

        for(int i=1;prime[i]*prime[i]<=r;i++)//与for(int i=1;i<=cnt;i++)的效果相同，这样写不用开LL，但是按照我的写***出现int*int的范围超过int的情况，出现RuntimeError的情况，所以prime数组要开LL 
        {
            for(int j=l/prime[i];j<=r/prime[i];j++)
            if(j>1) vis[j*prime[i]-l]=1;
        }

        for(int i=l;i<=r;i++)
        {
            if(!vis[i-l]) p[++cntp]=i;
            if(i==r) break;//int最大为2147483647，如果再+1，变成-2147483648，会无限循环下去；这里直接break是防止当输入的r=2147483647的情况 
        }

        for(int i=2;i<=cntp;i++)
        {
            int dis=p[i]-p[i-1];
            if(dis>mx) mxl=p[i-1],mxr=p[i],mx=dis;
            if(dis<mn) mnl=p[i-1],mnr=p[i],mn=dis; 
        }

        if(!mx) cout<<"There are no adjacent primes."<<endl;
        else cout<<mnl<<","<<mnr<<" are closest, "<<mxl<<","<<mxr<<" are most distant."<<endl;
    } 
}

总结

要学会的思想：
要求素数，我们可以通过排除合数求素数；
任何一个合数n都至少有一个质因子小于等于根号n；