1619： 【例 1】Prime Distance

1619： 【例 1】Prime Distance原题

【题目描述】
原题来自：Waterloo local，题面详见 POJ 2689

给定两个整数 L,RL,R，求闭区间 [L,RL,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。

【输入】
多组数据。每行两个数 L,RL,R。

【输出】
详见输出样例。

【输入样例】
2 17
14 17
【输出样例】
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
【提示】
数据范围与提示：

对于全部数据，1≤L<R<231,R−L≤1061≤L<R<231,R−L≤106 。

【分析】

　　本题数据个数不算多，但绝对值很大，逐个判断质数是行不通的，故采用筛选法过滤掉[L,R]内的所有合数。筛选质数有几个可优化之处：

　　1、任何一个int范围内的合数的最小质因数不超过sqrt(2147483647)=46637，只要能筛掉合数，不需要找出所有质因数，所以，在过滤[L,R]内的合数前可以准备一个质数表。

　　2、在准备质数表里可以考虑线性筛选，尽量为后面腾出点时间。

几个注意：

　　1、如果L=1，需注意特别处理，因为它不是质数也不是合数，后面算法都过滤不掉，直接令L=2就好。否则......（你懂的)

　　2、用质数表过滤[L,R]内的合数时，要考虑是质数本身还是质数的倍数。我们的质数表可以到46637，但L,R也可能较小，会有一倍的时候。

　　3、寻找最大最小差值，注意循环内要初始化差值和相应的数组。

　　4、如果你数据类型选择了int，注意别越界。比如我们想表达x²<=inf(这里inf取值0x7fffffff，即最大int值)，那么这样就会出现越界，应换个写法：x<=inf/x。如果想表达i<=inf（可能每次循环会给i增加一个值a,那么可以考虑加个条件：if(i<=inf-a)i+=a; else 退出操作)。

　　5、那些个输出的文字，你可能看不清楚的（比如中间的标点符号是中文状态的还是英文状态的，中间有没有空格，你未必看得清楚,一本通网站1001题很多初学者就错在看不清），复制最可靠，用变量替换掉数字就好。

【AC代码】

//1619： 【例 1】Prime Distance 
#include<iostream>
#include<cstring>
using namespace std;
int const N=1e6+5,inf=0x7fffffff; 
int a[N],p[N],b[N],c[N],l,r,minn,maxn,l1,r1,l2,r2,cnt,t,n;
void spr()
{
    for(int i=2;i<=inf/i;i++)
    {
        if(!p[i])//i未被标注即为质数 
        {
            p[i]=i;
            b[++cnt]=i;
        }
        for(int j=1;j<=cnt&&p[j]<=p[i]&&i<=inf/i/b[j];j++)
            p[i*b[j]]=b[j];
    }
 } 
int main(){
    spr();//生成质数表b[N]
    while(cin>>l)
    {
        if(l==1)l=2;
        cin>>r;
        maxn=0,minn=r;//初始化相邻质数差的最大最小值 
        l1=l2=r1=r2=0;//差值最小的相邻质数为l1,r1,差值最大的相邻两质数为l2,r2 
        memset(p,0,sizeof(p));
        for(int i=0;i<=r-l;i++)a[i]=l+i;//存入[l,r]间的所有数 
        for(int i=1;i<=cnt&&b[i]<=r/b[i];i++)//暴力列举所有质因数 
        {
            t=(b[i]-l%b[i])%b[i];//在[l,r]内寻找b[i]的第一个倍数，可能包括b[i]本身
            for(int j=t;j<=r-l;j+=b[i])
                if(b[i]<a[j])p[j]=1;//标记b[i]的倍数为合数 
        }
        n=0;//统计[l,r]内的质数个数 
        for(int i=0;i<=r-l;i++)if(!p[i])c[++n]=a[i];
        if(n<2)cout<<"There are no adjacent primes.
";
        else
        {
            t=c[1];
            for(int i=2;i<=n;i++)
            {
                if(minn>c[i]-t)minn=c[i]-t,l1=t,r1=c[i];
                if(maxn<c[i]-t)maxn=c[i]-t,l2=t,r2=c[i];
                t=c[i];
            }
            cout<<l1<<","<<r1<<" are closest, "<<l2<<","<<r2<<" are most distant.
";
        }
    }    
    return 0;
}