质数距离

AcWing-196-质数距离

分析

见《进阶指南》第138页。

实现

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1000010, M = 50010;
int idx1, primes1[M];
int idx2, primes2[N];
bool mark[N];

void get_primes1 (int n) {
    for (int i = 2; i <= n; ++ i) {
        if (mark[i] == false) primes1[++ idx1] = i;
        for (int j = 1; primes1[j] <= n / i; ++ j) {
            mark[i * primes1[j]] = true;
            if (i % primes1[j] == 0) break;
        }
    }
}

int main () {
    get_primes1(M - 10);
    int l, r;
    while (cin >> l >> r) {
        // ---------- 重置 ----------
        idx2 = 0;
        memset(mark, 0, sizeof(mark));

        for (int i = 1; i <= idx1; ++ i) {
            LL p = primes1[i];
            for (LL j = max(2LL, (l + p - 1) / p) * p; j <= r; j += p)
                mark[j - l] = true;
        }
        for (int i = 0; i <= r - l; ++ i)
            if (i + l >= 2 && mark[i] == false)
                primes2[++ idx2] = i + l;
        
        if (idx2 < 2) {
            cout << "There are no adjacent primes." << endl;
        } else {
            int min_pos = 1, max_pos = 1;
            for (int i = 1; i <= idx2 - 1; ++ i) {
                int dis = primes2[i + 1] - primes2[i];
                if (primes2[min_pos + 1] - primes2[min_pos] > dis) min_pos = i;
                if (primes2[max_pos + 1] - primes2[max_pos] < dis) max_pos = i;
            }
            cout << primes2[min_pos] << "," << primes2[min_pos + 1] << " are closest, ";
            cout << primes2[max_pos] << "," << primes2[max_pos + 1] << " are most distant." << endl;
        }
    }
    return 0;
}