HDU 素數判定問題詳解：n²+n+41 表達式的素數驗證

題目背景與敘述

這是一道經典的杭州電子科技大學（HDU）OJ 題目，編號常被稱為「素數判定」。題目給定一個著名的數學表達式 n² + n + 41，要求判斷當整數 n 在區間 [x, y] 內取值時（其中 -39 ≤ x < y ≤ 50），該表達式的值是否全為素數。

輸入輸出規範

• 輸入：多組測試數據，每行兩個整數 x, y。遇到 0 0 結束輸入，該行不處理。
• 輸出：對每組數據，若區間內所有 n 使表達式值均為素數，輸出 OK，否則輸出 Sorry，每行一組結果。

樣例說明

Sample Input
0 1
0 0

Sample Output
OK

當 n=0 時值為 41（素數），n=1 時值為 43（素數），故輸出 OK。

解題思路

表達式 n² + n + 41 是歐拉發現的著名生成素數多項式，在 n ∈ [0, 39] 時確實全為素數。但題目範圍擴展至 [-39, 50]，需逐一驗證。

演算法步驟：

1. 讀入 x, y 直到 0 0。
2. 對區間內每個 n 計算 z = n² + n + 41。
3. 判斷 z 是否為素數：遍歷 2 ~ √z，若有因數則非素數。
4. 若區間內任一 z 非素數，標記並輸出 Sorry，否則輸出 OK。

參考代碼（C 語言）

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

int main() {
    int x, y, n, z, a, flag;
    while (scanf("%d%d", &x, &y) != EOF && (x != 0 || y != 0)) {
        flag = 0;
        for (n = x; n <= y; n++) {
            z = n * n + n + 41;
            for (a = 2; a <= sqrt(z); a++) {
                if (z % a == 0) {
                    flag++;
                    break;
                }
            }
            if (flag) break;
        }
        if (flag == 0) printf("OK\n");
        else printf("Sorry\n");
    }
    return 0;
}

優化提示

• 預先建立素數表（篩法）可加速多次查詢。
• 注意 n 為負數時 n² 為正，邏輯不變。
• 題目數據範圍小，暴力判斷完全足夠。

總結

本題考察基本的素數判定與區間遍歷，關鍵在於正確理解表達式在給定範圍內的行為。歐拉多項式在 n=40 時產生 40²+40+41=1681=41² 非素數，故超出 [0,39] 後需謹慎驗證。