質數定義：大於 1 的自然數，除 1 與自身外無其他因數。判斷 n 是否為質數，只需檢查 2 到 √n 的整數是否能整除 n，因為若 n = a × b，則 a ≤ √n 或 b ≤ √n。
public class TestPrime {
// 判斷質數：試除至 sqrt(num)
public static boolean isPrime(int num) {
if (num < 2) return false;
int limit = (int) Math.sqrt(num);
for (int i = 2; i <= limit; i++) {
if (num % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
for (int n = 2; n <= 100; n++) {
if (isPrime(n)) {
System.out.println(n + " is a prime");
}
}
}
}2 is a prime
3 is a prime
5 is a prime
7 is a prime
11 is a prime
13 is a prime
17 is a prime
19 is a prime
23 is a prime
29 is a prime
31 is a prime
37 is a prime
41 is a prime
43 is a prime
47 is a prime
53 is a prime
59 is a prime
61 is a prime
67 is a prime
71 is a prime
73 is a prime
79 is a prime
83 is a prime
89 is a prime
97 is a prime共 25 個質數。
| 方法 | 時間複雜度 | 適用場景 |
|---|---|---|
| 試除法（至 √n） | O(√n) | 單一數值判斷、N ≤ 10^7 |
| 埃拉托斯特尼篩法 | O(N log log N) | 列出 2..N 所有質數、N ≤ 10^8 |
| 歐拉篩（線性篩） | O(N) | 大範圍質數表、需最小質因數分解 |
| Miller-Rabin 概率測試 | O(k log³ n) | 超大整數 (64-bit+) 質數判斷 |
public static List sieve(int n) {
boolean[] isComposite = new boolean[n + 1];
List primes = new ArrayList<>();
for (int i = 2; i <= n; i++) {
if (!isComposite[i]) {
primes.add(i);
if ((long)i * i <= n) {
for (int j = i * i; j <= n; j += i) {
isComposite[j] = true;
}
}
}
}
return primes;
} 篩法適合「一次產出範圍內所有質數」，試除法適合「單一數值反覆查詢」。
質數判斷是演算法入門經典。理解 √n 邊界的數學證明，能避免寫出 i < num 這類低效迴圈。實務上依據資料範圍選擇試除法、篩法或概率測試，才是工程師的正確態度。
