埃拉托斯特尼篩法 Java 實作：百萬內質數秒級篩選

經典演算法現代化：從 O(n log log n) 到位圖優化

埃拉托斯特尼篩法是尋找 N 以內所有質數的最高效演算法之一。本範例採用 int[] 標記法（0=質數、1=合數），核心雙重迴圈僅遍歷至 sqrt(N)，時間複雜度 O(N log log N)，空間 O(N)。N=99999 即時完成。

核心程式碼

public static void getPrimes(int n) {
    if (n < 2 || n > 1_000_000) throw new IllegalArgumentException("n 範圍 2~1,000,000");
    int[] mark = new int[n]; // 0:質數, 1:合數
    mark[0] = mark[1] = 1;   // 0、1 非質數

    // 關鍵：外層只跑到 sqrt(n)
    for (int i = 2; i * i < n; i++) {
        if (mark[i] == 0) { // i 是質數
            // 從 i*i 開始標記，步長 i
            for (int j = i * i; j < n; j += i) {
                mark[j] = 1;
            }
        }
    }

    // 輸出格式化：每行 10 個
    int count = 0, perRow = 10;
    System.out.println(n + " 以內的質數：");
    for (int i = 0; i < n; i++) {
        if (mark[i] == 0) {
            if (count % perRow == 0 && count != 0) System.out.println();
            System.out.print(i + "\t");
            count++;
        }
    }
}

關鍵優化細節

進階版：位圖法突破記憶體限制

// 使用 BitSet（JDK 內建位向量），N=1 億約 12.5 MB
BitSet isComposite = new BitSet(n);
for (int i = 2; i * i < n; i++) {
    if (!isComposite.get(i)) {
        for (int j = i * i; j < n; j += i) isComposite.set(j);
    }
}
// 遍歷輸出
for (int i = 2; i < n; i++) if (!isComposite.get(i)) primes.add(i);

更極致可用 long[] 手寫位圖，配合輪因子跳過 2、3、5 的倍數，達到 O(N log log N / 32) 運算與 N/32 空間。

應用場景

• 密碼學素數生成（需更大範圍配合 Miller-Rabin 檢測）。
• 數論題、質因數分解預處理。
• 面試手寫篩法考察邊界條件與優化思維。