Java判斷素數

隨著計算機科學的發展，人們對數學問題的研究越來越多地依賴於計算機技術。素數是一種基本而重要的數學概念，而Java是一種流行的、跨平台的編程語言，可以用來檢驗一個數是否為素數。在本文中，我們將研究如何在Java中判斷素數。

一、素數的定義

首先，我們需要了解素數的定義。素數是指除了1和它本身以外，不能被其它整數整除的數。例如，2、3、5、7、11等都是素數，而4、6、8、9等都不是素數。

二、判斷素數的方法

判斷素數的方法有很多種，下面分別介紹兩種：

1、基本演算法

最基本的判斷素數的演算法是判斷一個數n是否只能被1和n本身整除。這可以用一個循環來實現：

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

上面的代碼首先判斷n是否小於或等於1，如果是，則直接返回false。接下來，它用一個循環從2開始逐個檢查每個數是否是n的因子，如果n有其它因子，則這個數不是素數。

2、改進的演算法

上面的基本演算法雖然簡單易懂，但卻不夠高效。一個改進的演算法是只需要判斷n是否只能被2、3和大於等於5的素數整除，因為一個大於等於5的素數總是6n±1的形式，而6n、6n+2、6n+3、6n+4肯定不是素數。

public static boolean isPrime(int n) {
    if (n <= 1) return false;
    else if (n <= 3) return true;
    else if (n % 2 == 0 || n % 3 == 0) return false;
    int i = 5;
    while (i*i <= n) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
        i += 6;
    }
    return true;
}

上面的代碼先判斷n是否小於等於3，如果是，則直接返回true（因為2和3肯定是素數）。接下來，它判斷n是否能被2或3整除，如果能，則直接返回false。否則，它用一個while循環從5開始檢查每個6n±1是否是n的因子，如果n有其它因子，則這個數不是素數。循環結束後，如果n沒有其它因子，則這個數是素數。

三、測試代碼

下面的代碼演示了如何使用上面的兩種演算法來判斷一個數是否為素數：

public class Main {
    public static void main(String[] args) {
        int n = 23;
        if (isPrime(n)) System.out.println(n + "是素數");
        else System.out.println(n + "不是素數");
    }
    public static boolean isPrime(int n) {
        // 基本演算法
        // if (n <= 1) return false;
        // for (int i = 2; i*i <= n; i++) {
        //     if (n % i == 0) return false;
        // }
        // return true;
        
        // 改進的演算法
        if (n <= 1) return false;
        else if (n <= 3) return true;
        else if (n % 2 == 0 || n % 3 == 0) return false;
        int i = 5;
        while (i*i <= n) {
            if (n % i == 0 || n % (i + 2) == 0) return false;
            i += 6;
        }
        return true;
    }
}

對於n=23，上面的代碼輸出：23是素數。

四、總結

到此為止，我們已經學會了如何在Java中判斷素數。通常來說，改進的演算法比基本演算法更加高效。但具體使用哪個演算法，需要根據具體的應用場景來決定。同時，還需要注意代碼中的邊界條件，以避免出現意料之外的結果。希望這篇文章對你有所幫助！