POJ2689Prime Distance


这是区间筛素数的模板,由于l r过大,之间用埃筛一定会超时,由于r-l在接受范围内,所以先把1-根号r的素数预处理一遍,然后再用p*i统计l-r内的素数,注意l=1要特判

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000010;
int v[maxn],a[maxn],b[maxn],tot=0;
int l,r,x1,x2,y1,y2;
void prime()
{
    memset(v,0,sizeof(v));
    for(int i=2;i<=46340;i++)
    {
        if(v[i]) continue;
        a[++tot]=i;
        for(int j=i;j<=46340/i;j++) v[i*j]=1;    
    }
}
int main()
{
    prime();
    while(cin>>l>>r)
    {
        memset(v,0,sizeof(v));
        if(l==1) v[0]=1;
        for(int i=1;i<=tot;i++)
        {
            for(int j=l/a[i];j<=r/a[i];j++)
            {
                if(j>1) v[a[i]*j-l]=1;
            }
        }
        int m=0;
        for(int i=l;i<=r;i++)
        {
            if(v[i-l]==0) b[++m]=i;
            if (i == r) break;
        }


        int p1=2147483647;int p2=0;
        for(int i=1;i<m;i++)
        {
            int t=b[i+1]-b[i];
            if(t<p1)
            {
                p1=t;
                x1=b[i],x2=b[i+1];
            }
            if(t>p2)
            {
                p2=t;
                y1=b[i];
                y2=b[i+1];
            }
        }
        if(!p2) cout<<"There are no adjacent primes.\n";
        else cout<<x1<<','<<x2<<" are closest, "<<y1<<','<<y2<<" are most distant.\n";
    }
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
P1955 NOI2015程序自动分析 P1955 NOI2015程序自动分析
这道题其实就是把相等的两个点用并查集维护,首先通过排序把相等的放在前面建立集合,然后再通过不等判断是否处在同一集合,由于ij规模过大,要先离散化 #include<bits/stdc++.h> using namespace std
2019-07-05
下一篇 
P1886滑动窗口 P1886滑动窗口
单调队列的经典问题,维护两个单调队列,一个递增一个递减 #include<bits/stdc++.h> using namespace std; const int maxn=1e6+10; int n,k,a[maxn]; int
2019-07-05
  目录