问题描述:

我们定义素数的距离为两个相邻素数之间存在合数的个数。给你一个区间$[l, r]$你需要求出区间内距离最大和最小的两对素数

输入:

有多组数据,每组数据两个数l, r
其中l, r不超过2147483647,区间大小不超过1000000

输出:

如果不存在两个质数输出”There are no adjacent primes.”
否则输出 “x1,x2 are closest, y1,y2 are most distant.”其中x1,x2,y1,y2为两对距离最大和最小的素数

思路:

由于l, r都很大,所以不方便之间线性筛。但区间大小不超过1000000,所以我们要利用好这个条件。

由于区间较小,我们可以利用类似于筛的方法筛掉区间的合数。我们可以先预处理出$2^{16}$内的素数,对于每一个区间我们通过枚举素数$prime[i]$,把区间内为$prime[i]$的倍数标记。枚举了所有素数后,区间内没有标记的数就是素数了。然后$O(n)$扫一遍计算出答案。

代码:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define MAXN 2000005
#define LL long long
using namespace std;

int l, r, tot, v[MAXN], prime[MAXN];
bool vis[1000005];

void getprime(int n)
{
    for(int i=2; i<=n; i++)
    {
        if(!v[i]) prime[++tot]=i, v[i]=i;
        for(int j=1; j<=tot; j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i) break;
            v[i*prime[j]]=prime[j];
        }
    }
}

int main()
{
    getprime(MAXN-5);
    while(scanf("%d%d", &l, &r)!=EOF)
    {
        if(l==1) l++;
        int ans1, ans2, ans3, ans4, last=-1, maxn=-1, minn=1e9;
        memset(vis, 0, sizeof(vis));
        for(int j=1; j<=tot; j++)
        {
            int x=((LL)l+prime[j]-1)/prime[j], y=r/prime[j];
            for(int i=max(2, x); i<=y; i++) vis[prime[j]*i-l]=1;
        }

        for(int i=0; i<=r-l; i++)
        {
            if(vis[i]) continue;
            if(last==-1) {last=i; continue;}
            if(i-last>maxn)
            {
                maxn=i-last;
                ans1=last+l; ans2=i+l;
            }
            if(i-last<minn)
            {
                minn=i-last;
                ans3=last+l; ans4=i+l;
            }
            last=i;
        }
        if(maxn==-1) printf("There are no adjacent primes.\n");
        else printf("%d,%d are closest, %d,%d are most distant.\n", ans3, ans4, ans1, ans2);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注