Java 求質數算法演進：從暴力枚舉到埃拉托斯特尼篩法

質數定義

大於 1 的自然數，除 1 和自身外無其他因數。最小質數 2（唯一偶質數）。質數無限多（歐幾里得證明）。

三種算法對比

1. 暴力定義法 O(n²)

for (int i = 2; i < n; i++) {
    int count = 0;
    for (int j = 2; j <= i; j++) {
        if (i % j == 0) count++;
        if (count > 1) break;
    }
    if (count == 1) print(i);
}

雙重循環，效率極低。

2. 平方根優化法 O(n√n)

public static boolean isPrime(int num) {
    for (int j = 2; j <= Math.sqrt(num); j++) {
        if (num % j == 0) return false;
    }
    return true;
}

利用「因子成對出現，至少一個 ≤ √n」原理，大幅減少除法次數。

3. 動態質數表法（類埃拉托斯特尼篩）O(n log log n)

private static List<Integer> getPrimes(int n) {
    List<Integer> primes = new ArrayList<>();
    primes.add(2);
    for (int i = 3; i <= n; i += 2) { // 跳過偶數
        if (!divisible(i, primes)) primes.add(i);
    }
    return primes;
}

private static boolean divisible(int n, List<Integer> primes) {
    for (Integer p : primes) {
        if (n % p == 0) return true;
        if (p * p > n) break; // 關鍵優化：只需試除到 √n
    }
    return false;
}

核心思想：一個數若不能被所有比它小的質數整除，則它是質數。維護已知質數表，試除時提前終止（p² > n）。

性能對比（求 100 萬內質數）

• 暴力法：~10 秒
• 平方根法：~500 毫秒
• 動態質數表：~50 毫秒

工程建議

• 小範圍（< 10⁶）：動態質數表足夠。
• 大範圍（> 10⁷）：標準 埃拉托斯特尼篩法（位圖優化、分段篩）或 歐拉篩（線性篩） O(n)。
• 單次大數質數測試：Miller-Rabin 概率算法。