Java 求 100 以內質數（素數）經典範例

前言

質數判斷是程式設計入門常見練習。本文展示一個標準的 O(√n) 試除法實作，列印 1 到 100 之間的所有質數。

程式碼

package airthmatic;

public class PrimeDemo {
    public static void main(String[] args) {
        for (int i = 1; i <= 100; i++) {
            if (isPrime(i)) {
                System.out.print(i + " ");
            }
        }
    }

    /**
     * 判斷正整數是否為質數
     * @param n 待測數字
     * @return true 為質數
     */
    public static boolean isPrime(int n) {
        if (n < 2) return false;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) return false;
        }
        return true;
    }
}

執行結果

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 

演算法說明

• 只需測試除數至 √n，因若 n = a × b，則至少一因子 ≤ √n。
• 時間複雜度 O(n√n)，對 100 以內數字極快。
• 若需更大範圍，可改用「埃拉托斯特尼篩法」O(n log log n)。