Java判斷素數方法：試除法優化至√n與邊界處理

基礎試除法

public static boolean isPrime(int n) {
    if (n <= 1) return false; // 1非素數
    if (n <= 3) return true;  // 2,3是素數
    if (n % 2 == 0 || n % 3 == 0) return false; // 排除2、3的倍數
    
    // 只需檢查到 √n，步長6k±1優化
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

關鍵優化點

1. √n截斷：若n = a*b，至少一個因子≤√n。
2. 6k±1模式：除2、3外，所有素數鄰近6的倍數（5,7 / 11,13 / 17,19...），減少2/3循環次數。
3. 邊界處理：n<=1非素數，n=2,3直接返回。

完整可運行示例

import java.util.Scanner;

public class PrimeChecker {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("請輸入整數: ");
        int n = sc.nextInt();
        System.out.println(n + (isPrime(n) ? " 是" : " 不是") + " 素數");
    }
    
    public static boolean isPrime(int n) {
        if (n <= 1) return false;
        if (n <= 3) return true;
        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;
    }
}

大數素性測試（補充）

超過int範圍（>21億）或極大數（百位數）需概率算法：

• Miller-Rabin 測試（JavaBigInteger.isProbablePrime(certainty)）。
• 確定性版本：Baillie-PSW、AKS算法。

常見錯誤避坑

• 循環條件寫i < n導致O(n)超時。
• 忘記處理負數、0、1。
• 用Math.sqrt(n)引入浮點誤差，首選i*i <= n整數運算。