Prime Distance

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1756 字
多组数据，每组给[L,R]，求区间内相邻质数
一本通
例
正文

/*
原题：T1619「一本通 6.2 例 1」Prime Distance（POJ 2689）
题意：多组数据，每组给 [L,R]，求区间内相邻质数中差值最小与最大的数对（并列取靠前者）。
思路：区间长度 R-L 不大（题目保证 ≤1e6），用分段筛：先筛出 √R 以内的基质数，再标记 [L,R] 内的合数。
收集区间内所有质数，顺序扫描相邻差，分别维护最小差、最大差的首对。
复杂度：时间 O((R-L)loglogR + √R)，空间 O(R-L)
易错点：1) L 可能为 1，需显式标记 1 非质数；2) 质数起点从 2 开始；3) 不足两个质数时输出 "There are no adjacent primes."。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
vector<int> basePrimes(int lim){
    vector<bool> isp(lim+1,true);
    isp[0]=isp[1]=false;
    for(int i=2;i*i<=lim;i++){
        if(isp[i]){
            for(int j=i*i;j<=lim;j+=i){
                isp[j]=false;
            }
        }
    }
    vector<int> pr;
    for(int i=2;i<=lim;i++){
        if(isp[i]) pr.push_back(i);
    }
    return pr;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<int> bp=basePrimes(46341);
    ll L,R;
    while(cin>>L>>R){
        ll len=R-L+1;
        vector<bool> isp(len,true);
        if(L<=1) isp[1-L]=false;
        for(int p:bp){
            if((ll)p*p>R) break;
            ll start=max((ll)p*p,((L+p-1)/p)*p);
            for(ll m=start;m<=R;m+=p){
                isp[m-L]=false;
            }
        }
        vector<ll> pr;
        for(ll m=L;m<=R;m++){
            if(isp[m-L]) pr.push_back(m);
        }
        if(pr.size()<2){
            cout<<"There are no adjacent primes.\n";
            continue;
        }
        ll ca=pr[0],cb=pr[1],cg=pr[1]-pr[0];
        ll da=pr[0],db=pr[1],dg=pr[1]-pr[0];
        for(size_t i=1;i<pr.size();i++){
            ll g=pr[i]-pr[i-1];
            if(g<cg){ cg=g; ca=pr[i-1]; cb=pr[i]; }
            if(g>dg){ dg=g; da=pr[i-1]; db=pr[i]; }
        }
        cout<<ca<<","<<cb<<" are closest, "<<da<<","<<db<<" are most distant.\n";
    }
    return 0;
}
Prime Distance

正文

一本通·提高篇的其它内容
