大於 1 的自然數，除 1 和它本身外無其他因數。1 不是素數。
對 n 從 2 試除到 n-1，若存在能整除者則為合數，否則為素數。
#include <stdio.h>
#include <stdbool.h>
bool IsPrime(int val) {
if (val <= 1) return false; // 1 及負數非素數
for (int i = 2; i < val; i++) {
if (val % i == 0) return false;
}
return true;
}
int main(void) {
int data;
scanf("%d", &data);
printf(IsPrime(data) ? "yes\n" : "no\n");
return 0;
}
7 → yes 9 → no 13 → yes
| 優化 | 邏輯 | 複雜度 |
|---|---|---|
| √n 截斷 | 只試除到 sqrt(val)，因若 a*b=val 則必有一因子 ≤√n | O(√n) |
| 跳過偶數 | 先判 2，再從 3 步長 2 遍歷奇數 | O(√n/2) |
| 6k±1 模式 | 素數(>3)皆為 6k±1 形式，步長 6 檢查 i 和 i+2 | O(√n/3) |
| 預篩小素數 | 先用小素數表快速排除明顯合數 | 常數加速 |
bool IsPrimeOpt(int val) {
if (val <= 1) return false;
if (val <= 3) return true; // 2, 3
if (val % 2 == 0 || val % 3 == 0) return false;
for (int i = 5; i * i <= val; i += 6) {
if (val % i == 0 || val % (i + 2) == 0) return false;
}
return true;
}
32 位整數試除法足夠，64 位或大整數需用 Miller-Rabin 概率測試或 AKS 確定性算法。
試除法是理解素數判斷的入門算法，掌握 √n 截斷與 6k±1 優化可應對絕大多數面試與工程場景。實際項目中推薦使用成熟庫（如 OpenSSL、GMP）的素性測試函數。
