Java 尋找質數演算法實作：從基礎試除法到埃拉托斯特尼篩法

尋找質數是程式設計入門的經典題目，雖然概念基礎，但初學者常在實作細節上碰壁。無論是物件導向或程序導向語言，核心邏輯大同小異。本文提供兩種 Java 實作供參考：一般試除法與篩法。

一、一般試除法

最直觀的做法是對每個數字進行試除。為了效率，只需檢查到該數的平方根即可：若 2 到 √n 之間沒有因數，該數即為質數。

public class Prime {
    public static void main(String[] args) {
        for (int i = 2; i < 100; i++) {
            int j;
            for (j = 2; j < (int) (Math.sqrt(i) + 1); j++) {
                if (i % j == 0) {
                    break;
                }
            }
            if (j > (int) Math.sqrt(i)) {
                System.out.print(i + " ");
            }
        }
    }
}

關鍵點解析：

• 外層迴圈遍歷 2 到 99 的候選數。
• 內層迴圈只跑到 Math.sqrt(i) + 1，大幅減少除法次數。
• 若內層迴圈正常結束（j > Math.sqrt(i)），代表沒找到因數，輸出該質數。

二、埃拉托斯特尼篩法

篩法適合一次找出某範圍內所有質數，時間複雜度接近 O(n log log n)，比試除法快得多。核心思想：建立布林/整數陣列標記合數，逐步「篩」掉倍數。

public class Prime2 {
    public static void main(String[] args) {
        int n = 100;
        int[] array = new int[n];
        for (int i = 2; i < n; i++) {
            array[i] = i;
        }
        for (int i = 2; i < n; i++) {
            if (array[i] != 0) {
                int temp = array[i];
                for (int j = 2 * temp; j < n; j += temp) {
                    array[j] = 0;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (array[i] != 0) {
                System.out.print(i + " ");
            }
        }
    }
}

運作流程：

1. 初始化陣列，索引即數值（0、1 不用）。
2. 從 2 開始，若 array[i] != 0 則 i 為質數。
3. 將該質數的所有倍數標記為 0（合數）。
4. 最後遍歷陣列，非零即質數。

效能比較與選擇建議

實務上，若只需判斷單一大數是否為質數，可改用 Miller-Rabin 概率測試；若需在固定區間高頻查詢，預先跑篩法建表最划算。