题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long LL;

const int N = 1000010;

int primes[N], cnt;
bool st[N];

void init(int n)
{
    memset(st, 0, sizeof st);
    cnt = 0;
    for (int i = 2; i <= n; i ++)
    {
        if (!st[i]) primes[cnt ++] = i;
        for (int j = 0; primes[j] * i <= n; j ++)
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main()
{
    int l, r;
    while(cin >> l >> r)
    {
        init(50000);
        memset(st, 0, sizeof st);

        for (int i = 0; i < cnt; i ++)
        {
            LL p = primes[i];
            for (LL j = max(p * 2, (l + p - 1) / p * p); j <= r; j += p)
                st[j - l] = true;
        }

        cnt = 0;
        for (int i = 0; i <= r - l; i ++)
        {
            if (!st[i] && i + l >= 2) 
                primes[cnt ++] = i + l;
        }

        if (cnt < 2) puts("There are no adjacent primes.");
        else
        {
            int maxv = 0, minv = 0;
            for (int i = 0; i + 1 < cnt; i ++)
            {
                int d = primes[i + 1] - primes[i];
                if (d > primes[maxv + 1] - primes[maxv]) maxv = i;
                if (d < primes[minv + 1] - primes[minv]) minv = i;
            }
            printf("%d,%d are closest, %d,%d are most distant.\n", primes[minv], primes[minv + 1], primes[maxv], primes[maxv + 1]);
        }
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla