算法学习之路|POJ2689（素数筛）

题目大意：选出区间L,R之间相邻素数中差值最大和最小的素数对

素数筛（线性筛）：

#include<stdio.h>  
#include<string.h>
#include<iostream>
using namespace std;  
#define MAX 10000000
long long su[MAX],cnt;  
bool isprime[MAX];  
void prime()  
{  
    cnt=1;  
    memset(isprime,1,sizeof(isprime));//初始化
    isprime[0]=isprime[1]=0;//0和1不是素数  
    for(long long i=2;i<=MAX;i++)  
    {  
        if(isprime[i])  
            su[cnt++]=i;//保存素数
        for(long long j=1;j<cnt&&su[j]*i<MAX;j++)  
        {  
            isprime[su[j]*i]=0;//筛掉小于等于i的素数和i的积构成的合数  
        }  
    }  
}  
int main()  
{  
    prime();  
    for(long long i=1;i<cnt;i++)  
        printf("%d  ",su[i]);  
    return 0;  
}  

思路：直接用素数筛会超时（int范围线性复杂度时间复杂度已经达到10e9），而区间间隔比较小，只有1e6，而且对于int范围内的合数来说，最小质因子必定小于2^16。所以可以进行二次筛素数，第一次对50000以内筛素数，第二次筛出L,R区间内素数即可。

代码：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1e9
#define maxn 50005
#define maxm 100005
int l,u;
int su[maxn],isprime[maxn],f[maxm];
int cnt=0;
void prime()
{
    memset(isprime,1,sizeof(isprime));
    isprime[0]=isprime[1]=0;
    for(int i=2;i<=maxn;i++)
    {
        if(isprime[i])
            su[cnt++]=i;
        for(int j=1;j<cnt&&su[j]*i<maxn;j++)
        { 
            isprime[su[j]*i]=0; 
        }
    } 
} 
int main() 
{ prime(); 
    while(cin>>l>>u)
    {
        if(l==1)l=2;//注意l=1
        memset(f,0,sizeof(f));
        for(int i=0;i<cnt;i++)
        {
           int a=(l-1)/su[i]+1;
           int b=u/su[i];
            for(int j=a;j<=b;j++) if(j>1)
                f[j*su[i]-l]=1;
        }
        int p=-1,max_ans=-1,min_ans=INF,x1,y1,x2,y2;
        for(int i=0;i<=u-l;i++)//暴力枚举
        {
            if(f[i]==0)
            {
                if(p==-1)
                {
                    p=i;
                    continue;
                }
                if(max_ans<i-p) { max_ans=i-p; x1=p+l;y1=i+l; } if(min_ans>i-p)
                {
                    min_ans=i-p;
                    x2=p+l;y2=i+l;
                }
                p=i;
            }
        }
        if(max_ans==-1)cout<<"There are no adjacent primes."<<endl;
        else cout<<x2<<","<<y2<<" are closest, "<<x1<<","<<y1<<" are most distant."<<endl;
    }
    return 0;
}