题目描述

求给定区间 $[l,r]$ 内相邻距离最短的质数与距离最长的质数

对于快速判断大整数质数问题， 适宜使用 Miller_Robbin 算法， 实际密码学/数学软件中经常被利用。

Miller_Robbin 算法

时间复杂度 $O(TLk(logn)^3)$.
其中 $T$ 为数据组数， $L$ 为区间长度， $k$ 为测试循环次数。

为了加快速度，程序中对于数目较多的$2, 3, 5$ 的倍数进行了特判处理

算法原理

算法基于 $femat$ 小定理 $b ^ {p - 1} = 1 (mod\, p) , \,\,p \in prime. b$ 不为 $p$ 的倍数.

质数 $p$ 一定满足上述定理， 满足上述定理的整数 不一定为质数。

尽管如此，满足 $femat$ 小定理的合数占比极少， 因此可以通过设定参数 $k$, 实现多次检查，可证明， $k$ 次检查后仍为合数的概率至多为 $4 ^ {-k}$ . 容错率较高。

$qwq.$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>

#define N 20000007
#define int long long
#define ll long long
using namespace std;
bool ipri[N];
int pres[N], tot = 0, amin = N, amax = -N, l ,r, a0, a1, b0, b1;

ll ksm(ll a, ll b, ll p) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}
bool Miller_Robbin(ll x) {
    if (x == 1) return false;
    ll val = 0, bs2 = 1, b = 0; 
    for (int a = 1; a <= 10; a++) {
        b = rand() % x + 1;
        if (b == x) b--; bs2 = 1;
        while (((x - 1) / bs2) % 2 == 0) {
            val = ksm(b, (x - 1) / bs2, x);
            if (val != 1 && val != x - 1) return false;
            if (val == x - 1) break;
            bs2 <<= 1;
        }
        val = ksm(b, (x - 1) / bs2, x);
        if (val != 1 && val != x - 1) return false;
    }
    return true;
}
signed main() {
    while (cin >> l >> r) {
        a0 = a1 = b0 = b1 = 0;
        int las = 0; amin = N, amax = -N;
        for (int a = l; a <= r; a++) {
            if ((a % 2 == 0 && a != 2) || (a % 3 == 0 && a != 3) || (a % 5 == 0 && a != 5)) continue;
            if (Miller_Robbin(a)) {
                if (!las) las = a;
                else {
                    if (a - las > amax) {amax = a - las; b0 = las, b1 = a;}
                    if (a - las < amin) {amin = a - las; a0 = las; a1 = a;}
                }
                las = a;
            }
        }
        if (!a0 || !b0) printf("There are no adjacent primes.\n");
        else printf("%lld,%lld are closest, %lld,%lld are most distant.\n", a0, a1, b0, b1);
    }
    return 0;
}