Java 求 100 以內質數：試除法優化與平方根截斷技巧

質數定義

大於 1 的自然數，除 1 與自身外無其他因數。

核心判斷邏輯：試除法 + √n 截斷

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    if (n == 2) return true;        // 2 是唯一偶質數
    if (n % 2 == 0) return false;   // 排除偶數
    for (int i = 3; i <= Math.sqrt(n); i += 2) { // 只檢查奇數
        if (n % i == 0) return false;
    }
    return true;
}

為什麼只檢查到 √n？

若 n = a × b，則 a ≤ √n 或 b ≤ √n。若在 [2, √n] 找不到因數，大於 √n 的因子也不可能存在。

完整列印 100 以內質數

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

輸出：

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 

效能優化對比

6k±1 進階版

public static boolean isPrimeFast(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;       // 2, 3
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

原理：所有質數（>3）皆可表示為 6k±1 形式。

大範圍質數篩選：埃拉托斯特尼篩法

public static void sieve(int limit) {
    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;
        }
    }
    for (int i = 2; i <= limit; i++) if (isPrime[i]) System.out.print(i + " ");
}

時間複雜度 O(n log log n)，適用於 n > 10⁶ 批量求質數。