C語言素數判斷練習：n²+n+41 在區間內是否全為素數

C語言素數判斷練習：n²+n+41 在區間內是否全為素數

經典題目：驗證多項式 f(n)=n²+n+41 在 x≤n≤y (-39≤x

解題代碼

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

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

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

技巧點

• while (scanf(...)==2 && (x||y))：讀取成功且非雙零才處理。
• 提前 break 避免無謂計算。
• n*n 可能溢出 int (n≤50 時最大 2551，安全)；大範圍用 long long。

數學背景

歐拉多項式 n²+n+41 在 n=0~39 連產 40 個素數，n=40 時 40²+40+41=1681=41² 為合數。題目範圍含負數，負數代入結果同正數 (偶函數特性)，故仍需檢查。