對於表達式 f(n) = n² + n + 41，給定區間 [x, y] (-39 ≤ x ≤ y ≤ 50)，判斷該區間所有整數 n 代入後的值是否**全為質數**。輸出 OK 或 Sorry。多組測資，0 0 結束。
n² + n + 41 是著名的**尤拉質數多項式**，對 n = 0~39 產生 40 個質數。但 n = 40 時 40²+40+41 = 1681 = 41² 為合數。本題範圍含負數與超過 39 的值，需實際判定。
區間長度 ≤ 90 (從 -39 到 50)，每個值最大 50²+50+41 = 2591，開根號約 51。試除法極快。
#include#include // 判斷質數 (n > 1) int is_prime(int n) { if (n <= 1) return 0; if (n <= 3) return 1; // 2, 3 if (n % 2 == 0 || n % 3 == 0) return 0; // 6k ± 1 優化 for (int i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % (i + 2) == 0) return 0; } return 1; } int main() { int x, y; while (scanf("%d %d", &x, &y) == 2) { if (x == 0 && y == 0) break; int ok = 1; for (int n = x; n <= y; n++) { int val = n * n + n + 41; if (!is_prime(val)) { ok = 0; break; } } printf("%s\n", ok ? "OK" : "Sorry"); } return 0; }
預計算 [-39, 50] 所有值的質數性，查詢 O(1)。
#include#include #define MIN_N -39 #define MAX_N 50 #define MAX_VAL (MAX_N*MAX_N + MAX_N + 41) // 2591 int prime[MAX_VAL + 1]; void sieve() { for (int i = 0; i <= MAX_VAL; i++) prime[i] = 1; prime[0] = prime[1] = 0; for (int i = 2; i * i <= MAX_VAL; i++) { if (prime[i]) { for (int j = i * i; j <= MAX_VAL; j += i) prime[j] = 0; } } } int main() { sieve(); int x, y; while (scanf("%d %d", &x, &y) == 2) { if (x == 0 && y == 0) break; int ok = 1; for (int n = x; n <= y; n++) { int val = n * n + n + 41; if (!prime[val]) { ok = 0; break; } } printf("%s\n", ok ? "OK" : "Sorry"); } return 0; }
| 細節 | 處理 |
|---|---|
| 負數 n | n*n 為正，公式正常運算。範圍含負數需正確迴圈 for (n=x; n<=y; n++) |
| 值為 1 或負數 | is_prime 需處理 n <= 1 回傳 0 (本題最小值 n=-39 → 1481 > 1，無負值) |
| 平方溢位 | int 32 位足夠 (最大 2591)，無溢位風險 |
| 輸入結束 | 0 0 不處理，直接 break |
| 輸入 | 輸出 | 說明 |
|---|---|---|
| 0 1 0 0 | OK | n=0→41, n=1→43 皆質數 |
| 0 39 0 0 | OK | 尤拉 40 個質數 |
| 0 40 0 0 | Sorry | n=40 為 41² 合數 |
| -39 50 0 0 | Sorry | 全區間含合數 |
| 40 40 0 0 | Sorry | 單點測試 n=40 |
| 方法 | 預處理 | 單次查詢 | 空間 |
|---|---|---|---|
| 試除法 (6k±1) | 無 | O((y-x+1) × √val) ≈ 90×50 = 4500 操作 | O(1) |
| 埃氏篩預計算 | O(MAX_VAL log log MAX_VAL) ≈ 2591 | O(y-x+1) ≈ 90 查表 | O(MAX_VAL) ≈ 2.6KB |
兩者在本題規模下皆瞬間完成。篩法適合大量查詢、試除法適合單次/少量查詢。
本題考察：質數判定基礎 (試除法/篩法)、區間遍歷、邊界條件 (負數/0/1)、輸入終止處理。尤拉多項式 n²+n+41 是數論經典教材，理解其在 n=0~39 產生質數、n=40 失效的數學原因 (模 41 同餘)，能加深對質數分布的直覺。
