您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

UVA 10140 Prime Distance - 區間素數鄰距極值

編輯：C++ 入門

題目大意

給定區間 [L, R] (R ≤ 2,147,483,647, R-L ≤ 1,000,000)。
求區間內相鄰素數的最小間距與最大間距對應的素數對。無相鄰素數輸出 There are no adjacent primes.。

解法：區間篩法 (Segmented Sieve)

預處理：小素數表

先用埃氏篩求出 √R ≤ 46340 以內所有素數（約 4800 個）。

區間篩選

建立 vis[R-L+1] 標記合數
對每個小素數 p，從 ceil(L/p)×p 開始步長 p 標記
特殊處理 L=1 或 0

起始位置計算技巧

ll start = (L + p - 1) / p * p;  // ceil(L/p)*p
if (start == p) start += p;      // p 本身是素數，不標記

完整程式碼

#include <cstdio>
#include <cmath>
#include <cstring>
typedef long long ll;

const int LIM = 50000;
int prime[LIM], pcnt;
bool vis[LIM];
bool seg[1000005];

void sieve() {
    for (int i = 2; i < LIM; i++) if (!vis[i]) {
        prime[pcnt++] = i;
        for (int j = i+i; j < LIM; j += i) vis[j] = true;
    }
}

int main() {
    sieve();
    ll L, R;
    while (scanf("%lld%lld", &L, &R) == 2) {
        int len = R - L + 1;
        memset(seg, 0, sizeof(bool)*len);
        
        for (int i = 0; i < pcnt; i++) {
            ll p = prime[i];
            if (p * p > R) break;
            ll start = (L + p - 1) / p * p;
            if (start == p) start += p;
            for (ll j = start; j <= R; j += p)
                seg[j - L] = true;
        }
        
        // 收集素數
        static int primes[1000005], cnt;
        cnt = 0;
        for (ll i = L; i <= R; i++)
            if (!seg[i-L] && i > 1) primes[cnt++] = i - L;
        
        if (cnt <= 1) {
            puts("There are no adjacent primes.");
        } else {
            int min_d = 1e9, max_d = 0, min_i, max_i;
            for (int i = 1; i < cnt; i++) {
                int d = primes[i] - primes[i-1];
                if (d < min_d) { min_d = d; min_i = i; }
                if (d > max_d) { max_d = d; max_i = i; }
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",
                   primes[min_i-1]+L, primes[min_i]+L,
                   primes[max_i-1]+L, primes[max_i]+L);
        }
    }
    return 0;
}