题目描述

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

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

样例

输入样例：
2 17
14 17
输出样例：
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

算法(米勒-拉宾素性检验)

(暴力枚举) $O((u - l)klog(u - l)$

米勒-拉宾素性检验可以在$O(klogn)$的时间复杂度内判断一个数n是不是质数，k取决于迭代次数。
这个板子取了固定7个数迭代检验，所以k=7，并且用这7个数检验能正确检验long long范围内所有的素数。

参考文献

知乎：算法学习笔记(48): 米勒-拉宾素性检验—Pecco

C++ 代码

#include<bits/stdc++.h>
using namespace std;

const int INF = 0x7fffffff;

typedef long long ll;

int qpow(int a, int b, int p)
{
    int ans = 1;
    for (; b; b >>= 1)
    {
        if (b & 1) ans = (ll)ans * a % p;
        a = (ll)a * a % p;
    }
    return ans;
}

int isprime(int x)
{

    if (x < 3) return x == 2;
    if (x % 2 == 0) return 0;
    int A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, d = x - 1, r = 0;
    while (d % 2 == 0)
        r++, d /= 2;
    for (int a : A)
    {
        int v = qpow(a, d, x);
        if (v <= 1 || v == x - 1)
            continue;
        for (int i = 1; i <= r; i++)
        {
            v = (ll)v * v % x;
            if (v == x - 1 && i != r)
            {
                v = 1;
                break;
            }
            if (v == 1)
                return 0;
        }
        if (v != 1)
            return 0;
    }
    return 1;
}

int main()
{
    int l, u;
    while (cin >> l >> u)
    {
        int maxn = 0, minn = INF, maxx, maxy, minx, miny;
        int last = 0;
        for (unsigned int i = l; i <= u; i++)
        {
            if (isprime(i))
            {
                if (last != 0)
                {
                    if (i - last > maxn)
                        maxn = i - last, maxx = last, maxy = i;
                    if (i - last < minn)
                        minn = i - last, minx = last, miny = i;
                }
                last = i;
            }
        }
        if (maxn == 0) printf("There are no adjacent primes.\n");
        else printf("%d,%d are closest, %d,%d are most distant.\n", minx, miny, maxx, maxy);
    }
    return 0;
}