申論題

為了判斷一個數字 n 是否為質數，並假設我們已經有一個陣列 PrimeAry 存儲了所有小於 n 的質數，我們可以透過遍歷這個陣列來檢查 n 是否能被陣列中的任何質數整除。如果 n 不能被任何小於它的質數整除，則 n 是一個質數；否則，n 不是質數。這種方法的效率比起傳統的檢查方式高，因為它只需檢查到 n
​
  以內的質數即可。

以下是實現 IsPrime 函數的程式碼範例：

public class PrimeCheck {
    
    // 假設 PrimeAry 是一個已排序且儲存所有小於 n 的質數的陣列
    static int[] PrimeAry = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31}; 

    // 函數 IsPrime 用於判斷 n 是否為質數
    public static boolean IsPrime(int n) {
        // 處理邊界條件
        if (n <= 1) {
            return false;
        }
        
        // 只需檢查到 sqrt(n) 即可
        int sqrtN = (int)Math.sqrt(n);
        
        for (int prime : PrimeAry) {
            if (prime > sqrtN) {
                break; // 如果質數大於 sqrt(n)，則不再檢查
            }
            if (n % prime == 0) {
                return false; // 如果 n 能被陣列中的質數整除，則 n 不是質數
            }
        }
        
        return true; // 如果 n 不能被任何小於它的質數整除，則 n 是質數
    }

    public static void main(String[] args) {
        System.out.println(IsPrime(3)); // 應該回覆 True
        System.out.println(IsPrime(4)); // 應該回覆 False
    }
}
在這段程式碼中，IsPrime 函數首先檢查 n 是否小於等於 1（這些情況下 n 不是質數）。然後，函數計算 n 的平方根（sqrtN），並遍歷 PrimeAry 陣列中的每一個質數。如果陣列中的質數大於 sqrtN，則函數結束檢查，因為超過 sqrtN 的質數不可能整除 n。如果找到一個質數能整除 n，則 n 不是質數，函數返回 false。如果陣列中沒有任何質數能整除 n，則函數返回 true，表示 n 是質數。