AcWing 196. 质数距离

题目描述：

给定两个整数 L 和 U，你需要在闭区间 [L,U] 内找到距离最接近的两个相邻质数 C1 和 C2（即 C2−C1 是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数 D1 和 D2（即 D1−D2 是最大的），如果存在相同距离的其他相邻质数对，则输出第一对

思路：

先看数据范围是2³¹ – 1，巨大，不能直接筛出[l, r]的素数，但是规定了区间长度最多1e6

根据一个合数n至少有一个小于等于$\sqrt{n}$的质因子，我们可以先搞出前50000的数的素数，用这些素数去筛掉区间[l, r]内的合数，剩下的就是素数了，然后暴力跑就行

注意点：

• 数据范围巨大，需要将[l, r]离散化到[0, r – l]
• 对于一个素数p，筛[l, r]的起点应该是$max(2 * p, (l + p - 1) / p * p)$,至少是2 * p，因为p是素数，2 * p以外才是合数
• 搞出[l, r]的素数的时候要特判1的存在
• 开long long，不开见祖宗！
• 数组记得开到1e6

/*
Work by: Chelsea
Problem: 不知名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/

#include<map>
#include<set>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<cstdio>
#include<string>
#include<vector>
#include<sstream>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;

#define eps 1e-8
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define NMAX 1000 + 50
#define ls p<<1
#define rs p<<1|1
#define mod 998244353
#define y1 y114514
#define lowbit(x) (x & (-x))
#define sz(s) (int)(s).size()
#define sd(n) scanf("%d",&n)
#define sl(n) scanf("%lld",&n)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define sll(n,m) scanf("%lld %lld",&n,&m)
#define pd(n) printf("%d\n", (n))
#define pdd(n,m) printf("%d %d\n",n, m)
#define sddd(n,m,z) scanf("%d %d %d",&n,&m,&z)
#define slll(n,m,z) scanf("%lld %lld %lld",&n,&m,&z)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
#define m_p(a,b) make_pair(a, b)
//#define int long long
typedef long long ll;
typedef pair <int,int> pii;
typedef unsigned long long ull;
//不开longlong见祖宗!
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

//不改范围见祖宗!!!
#define MAX 300000 + 50
int n, m, k, op;
int x, y, z;
ll a, b, c, d;
string s, t;

ll l, r;
int tot;
bool vis[50050];
int prime[50050];

void init(int n){
    for(int i = 2; i <= n; ++i){
        if(!vis[i])prime[++tot] = i;
        for(int j = 1; i * prime[j] <= n && j <= tot; ++j){
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0)break;
        }
    }
}
bool vv[1000005];
void work(){
    init(50000);
    while(cin>>l>>r){
        mem(vv, 0);
        for(int i = 1; i <= tot; ++i){
            ll p = prime[i];
            for(ll j = max(2 * p, (l + p - 1) / p * p); j <= r; j += p){
                vv[j - l] = 1;
            }
        }
        vector<ll>pri;
        for(ll i = 0; i <= r - l; ++i){
            if(!vv[i] && i + l > 1){
                pri.push_back(i + l);
            }
        }
//        for(auto i : pri)cout<<i<<' ';
//        cout<<endl;
        if(pri.size() < 2)cout<<"There are no adjacent primes.\n";
        else{
            ll maxn = -inf, minx = inf;
            for(int i = 1; i < pri.size(); ++i){
                ll dd = pri[i] - pri[i - 1];
                if(dd < minx){
                    minx = dd;
                    a = pri[i - 1];b = pri[i];
                }
                if(dd > maxn){
                    maxn = dd;
                    c = pri[i - 1];d = pri[i];
                }
            }
            cout<<a<<','<<b<<" are closest, "<<c<<','<<d<<" are most distant.\n";
        }
        
    }
    
}


int main(){
    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}