「UVa 10140」Prime Distance

发表于 | | 阅读次数:
字数统计: 550 字

Description

题目链接：UVa 10140

给定区间 $[L,R]$，求这个区间中相邻的两个质数的差的最小值和最大是分别是多少，并输出对应的 $2$ 个质数；如果没有则输出 There are no adjacent primes.。

本题多组数据。

数据范围：$1\le L<R<2^{31}$，$R-L\le 10^6$

Solution

首先我们发现：$R-L$ 的范围很小，我们应该要能够快速求出 $L\sim R$ 之间的质数。

显然有推论：任意一个合数 $x$ 必定包含一个不超过 $\sqrt x$ 的质因子。

所以我们可以筛出 $[1,\sqrt R]$ 之间的所有质数，对于每个质数 $p$，把 $[L,R]$ 中能被 $p$ 整除的数标记为合数。最终没有被标记的数就是质数，对相邻的质数两两比较，找出差值最小和最大的即可。

时间复杂度：$O(\sum_{p\le \sqrt R}\frac{R-L}{p})=O(\sqrt R\log^2\sqrt R+(R-L)\log^2 R)$（该复杂度摘自：李煜东《算法进阶指南》）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
#include <cstdio>
#include <cstring>

const int N=1e6+5;
int tot,p[N];
bool flg[N],vis[N];

void init() {
    for(int i=2;i<N;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<N;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
void chkmin(long long &x,long long a,long long b,long long &p1,long long &p2) {
    if(x>b-a) x=b-a,p1=a,p2=b;
}
void chkmax(long long &x,long long a,long long b,long long &p1,long long &p2) {
    if(x<b-a) x=b-a,p1=a,p2=b;
}
int main() {
    init();
    long long l,r;
    while(~scanf("%lld%lld",&l,&r)) {
        memset(vis,1,sizeof(vis));
        if(l==1) vis[0]=0;
        for(int i=1;i<=tot;++i) {
            for(long long j=l/p[i];j*p[i]<=r;++j) {
                long long x=p[i]*j;
                if(j>1&&x>=l) vis[x-l]=0;
            }
        }
        long long p=0,p1,p2,p3,p4,mn=1LL<<60,mx=0;
        for(long long i=l;i<=r;++i) {
            if(!vis[i-l]) continue;
            if(p) chkmin(mn,p,i,p1,p2),chkmax(mx,p,i,p3,p4);
            p=i;
        }
        if(!mx) puts("There are no adjacent primes.");
        else printf("%lld,%lld are closest, %lld,%lld are most distant.\n",p1,p2,p3,p4);
    }
    return 0;
}
0%