Java 計算 100 以內質數的經典演算法範例

前言

質數又稱素數，指大於 1 的自然數中，除了 1 和它本身以外無其他因數的數。求 100 以內質數是程式設計入門的經典練習，本文提供標準試除法實現，並說明優化思路。

演算法邏輯：試除法

對每個候選數 n (3~100)，嘗試用 2 到 n-1 的整數去除。若無法整除，則為質數。為優化效能，實際只需檢查到 √n 即可，但本範例為教學清晰採用完整範圍。

完整代碼範例

package com.example.math;

public class PrimeNumberFinder {
    public static void main(String[] args) {
        int count = 0; // 統計質數個數，用於換行格式化

        System.out.println("100 以內的質數有：");
        // 2 是唯一的偶數質數，單獨處理
        System.out.print("2\t");
        count++;

        // 從 3 開始，只檢查奇數（偶數必非質數）
        for (int n = 3; n <= 100; n += 2) {
            boolean isPrime = true;
            // 只需檢查到 sqrt(n)，大幅減少循環次數
            for (int i = 3; i * i <= n; i += 2) {
                if (n % i == 0) {
                    isPrime = false;
                    break; // 找到因數，提前結束內層循環
                }
            }

            if (isPrime) {
                System.out.print(n + "\t");
                count++;
                // 每行輸出 6 個換行
                if (count % 6 == 0) {
                    System.out.println();
                }
            }
        }
        System.out.println("\n共找到 " + count + " 個質數。");
    }
}

代碼優化解析

1. 跳過偶數檢查

外層循環 n += 2、內層 i += 2，直接排除所有偶數，運算量減半。

2. 平方根截斷

內層循環條件 i * i <= n 等價於 i <= Math.sqrt(n)，避免浮點運算且更高效。若 n 有因數，必有一個 ≤ √n。

3. 格式化輸出

使用計數器 count 配合取模運算，每 6 個換行，輸出整齊美觀。

進階延伸：埃拉托斯特尼篩法

若需求更大範圍（如 100萬以內），試除法過慢。篩法 時間複雜度 O(n log log n)，極高效：

// 篩法核心邏輯
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);
isPrime[0] = isPrime[1] = false;
for (int i = 2; i * i <= limit; i++) {
    if (isPrime[i]) {
        for (int j = i * i; j <= limit; j += i) {
            isPrime[j] = false;
        }
    }
}

總結

本範例展示了試除法的標準實現與關鍵優化（僅檢查奇數、平方根截斷），代碼簡潔易懂，適合初學者理解迴圈控制與數學邏輯轉換。實際專案中若涉及大量質數運算，請改用篩法或概率性檢測（如 Miller-Rabin）。