Java 求小於 n 的質數 (素數) 三種算法實現與性能對比

質數定義

大於 1 的自然數，除 1 和自身外無其他因數。最小質數 2 (唯一偶質數)，其餘皆為奇數。質數無限多。

算法一：定義法 (暴力雙循環) — O(n²)

public static void printPrimeBasic(int 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) System.out.print(i + " ");
    }
}

最直觀，效率最低，n=100000 耗時秒級。

算法二：平方根優化 — O(n√n)

public static boolean isPrimeSqrt(int num) {
    if (num < 2) return false;
    for (int i = 2; i * i <= num; i++) { // i <= Math.sqrt(num)
        if (num % i == 0) return false;
    }
    return true;
}
public static void printPrimeSqrt(int n) {
    for (int i = 2; i < n; i++)
        if (isPrimeSqrt(i)) System.out.print(i + " ");
}

利用「若有因數，必有一個 ≤ √n」原理，大幅減少除法次數。n=100000 耗時 ~100ms。

算法三：埃拉托斯特尼篩法 / 線性篩 — O(n log log n) / O(n)

核心思想：**用已找到的質數去篩除合數**，避免重複除法。

3.1 埃氏篩 (經典)

public static List sieveEratosthenes(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; // 從 i*i 開始標記
        }
    }
    return primes;
}

3.2 線性篩 (歐拉篩) — 真正 O(n)

public static List sieveLinear(int n) {
    int[] lp = new int[n + 1]; // 最小質因數
    List primes = new ArrayList<>();
    for (int i = 2; i <= n; i++) {
        if (lp[i] == 0) { lp[i] = i; primes.add(i); }
        for (int p : primes) {
            if (p > lp[i] || (long)i * p > n) break;
            lp[i * p] = p; // 每個合數僅被最小質因數標記一次
        }
    }
    return primes;
}

性能對比 (n = 1,000,000)

// 定義法        : ~45 秒 (不可用)
// 平方根優化    : ~1.2 秒
// 埃氏篩        : ~30 ms
// 線性篩        : ~25 ms (最快，且得出最小質因數表)

工程應用建議

• **單次判斷大數質數** (如 64 位) 用 Miller-Rabin 概率測試。
• **批量求區間質數** 用線性篩，同時獲得最小質因數表，利於後續因數分解。
• **位圖優化** : boolean[] 可換為 BitSet 或 long[] 位操作，內存降低 8 倍。
• **分段篩** : 超大 n (1e12+) 時分塊處理，內存常數級。

總結

從暴力到線性篩，質數算法展現了「利用已知信息減少重複計算」的算法美學。**業務中直接用線性篩模板**，既快又能得 lp 數組，一舉多得。