POJ 2689

题意：求[l, r]区间中的间隔距离最大与最小的相邻两个素数，r<2200000000, r-l<10^6

题解：

　　对于<a的合数，其必然存在一个素因子b<=sqrt(a)。

　　因此先预处理出所有sqrt（MAXINT）的素数，之后对[l, r]区间进行筛法求素数即可

#include <cstdio>
#include <cmath>
#include <cstring>
#define LL long long
#define MAXN 2200000000

LL l, r, all;
bool pd[1000005];
LL num[10005];

int main()
{
    pd[1]=1;
    for(LL i=1; i*i < MAXN; i++)
        if(!pd[i])
        {
            num[all++]=i;
            for(LL j=i+i; j*j < MAXN; j+=i)
                pd[j]=1;
        }
    while(scanf("%lld%lld", &l, &r) != EOF)
    {
        memset(pd, 0, sizeof(pd));
        for(LL i=0; i < all && num[i]*num[i] <= r; i++)
            for(LL j=(((l+num[i]-1)/num[i]>1)?(l+num[i]-1)/num[i]:2)*num[i]; j <= r; j+=num[i])
                pd[j-l]=1;
        LL close1=0, close2=MAXN, dis1=0, dis2=-1, last=0;
        for(LL i=l; i <= r; i++)
            if(!pd[i-l] && i != 1)//1
            {
                if(i-last < close2-close1 && last != 0)
                    close2=i, close1=last;
                if(i-last > dis2-dis1 && last != 0)
                    dis2=i, dis1=last;
                last=i;
            }
        if(close1 == 0)
            printf("There are no adjacent primes.
");
        else
            printf("%lld,%lld are closest, %lld,%lld are most distant.
", close1, close2, dis1, dis2);
    }
    return 0;
}