OJ題解：素數判定 - 驗證 n²+n+41 在區間內全為質數

題目背景

歐拉多項式 f(n) = n² + n + 41 在 n ∈ [-39, 50] 時產生質數。輸入多組區間 [x, y]，判定該區間內所有整數 n 代入結果是否全為質數。

演算法

1. 雙重循環：外層遍歷 n = x .. y，內層試除法判質
2. 試除上限 sqrt(n) 即可（原代碼用 n/2 較慢但正確）
3. 任一合數即標記 mark=0 並跳出

完整原始碼

#include <stdio.h>
#include <math.h>

int is_prime(int n) {
    if (n < 2) return 0;
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return 0;
    return 1;
}

int main() {
    int x, y, n, ok;
    while (scanf("%d %d", &x, &y) == 2 && (x || y)) {
        ok = 1;
        for (n = x; n <= y; n++) {
            if (!is_prime(n*n + n + 41)) { ok = 0; break; }
        }
        printf(ok ? "OK\n" : "Sorry\n");
    }
    return 0;
}

優化說明

• 試除上限優化至 i*i <= n (等價 i <= sqrt(n))
• 提前結束：發現合數即跳出雙重循環
• 函數化 is_prime 結構更清晰

數學補充

n²+n+41 在 n=0..39 確實全為質數；n=40 時值為 40²+40+41=1681=41² 為合數。題目區間上限 50 包含此反例。