如何判斷一個數是不是質數

質數是指只能被1和自己整除的正整數，例如2、3、5、7、11、13等等。判斷一個數是否為質數是數學中的基本問題之一，本文將介紹多種方法來判斷一個數是否為質數。

一、試除法

試除法是最基本的一種方法，其思路是嘗試用2到該數的平方根的所有整數去除該數，如果都不能整除，那麼該數就是質數。相反，如果有一個數可以整除該數，那麼該數就不是質數。

def is_prime(n):
    if n <= 1:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

對於傳入的n，首先判斷其是否小於等於1，因為1不是質數。然後用一個循環從2到n的平方根來逐個判斷是否可以整除n，如果可以整除，那麼n就不是質數，直接返回False；否則n就是質數，返回True。

二、埃氏篩法

埃氏篩法是一種非常高效的篩選質數的方法，它的思路是從2開始，將所有能被2整除的數標記為合數，然後再以3為起點，將所有能被3整除的數標記為合數。不斷重複這個過程，就能將小於等於n的質數全部篩選出來。

def eratosthenes(n):
    if n <= 1:
        return []
    nums = [i for i in range(2, n+1)]
    i = 0
    while i = len(nums):
            break
    return nums

對於傳入的n，首先判斷其是否小於等於1，因為1不是質數。然後初始化一個數組nums，用於存儲2到n的所有整數。接著用一個循環，依次取出數組中的每個質數p，然後將所有能被p整除的數從數組中刪除，最後返回剩下的數組即為所有小於等於n的質數。

三、費馬小定理

費馬小定理是一種用於判斷質數的數論定理，其核心思想是通過快速冪來進行模運算，從而判斷一個數是否為質數。

def is_prime_fermat(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    for i in range(k):
        a = random.randint(2, n - 2)
        if pow(a, n - 1, n) != 1:
            return False
    return True

對於傳入的n，首先判斷其是否小於等於1，因為1不是質數。然後判斷n是否等於2或3，如果是，則n為質數。接著進行k次隨機測試，每次隨機選擇一個2到n-2之間的整數a，判斷是否滿足a^(n-1) ≡ 1 (mod n)，如果所有的測試都通過了，那麼n就可能是質數，返回True。注意，這裡的k表示進行測試的次數，k越大，誤判為質數的概率就越小。

四、米勒-拉賓素數檢驗

米勒-拉賓素數檢驗是一種基於費馬小定理進行改進的演算法，其思路是先將n-1分解成2^s * t的形式，然後隨機選擇一個2到n-2之間的整數a，計算a^t mod n的值，如果等於1或n-1，那麼n可能是質數。否則，不斷將a^t mod n進行平方運算，並檢查結果是否等於n-1。如果能夠通過k次測試，那麼就認為n是質數。

def miller_rabin(n, k=5):
    if n <= 1:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    s = 0
    t = n - 1
    while t % 2 == 0:
        t //= 2
        s += 1
    for i in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, t, n)
        if x == 1 or x == n - 1:
            continue
        for j in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

對於傳入的n，首先判斷其是否小於等於1，因為1不是質數。然後判斷n是否等於2或3，如果是，則n為質數。接著判斷n是否為偶數，如果是，則n不是質數。然後將n-1分解成2^s * t的形式，其中t是奇數，s是非負整數。接著進行k次隨機測試，每次隨機選擇一個2到n-2之間的整數a，計算a^t mod n的值，如果等於1或n-1，那麼繼續下一輪循環。否則，不斷將a^t mod n進行平方運算，並檢查是否等於n-1。如果k次測試都通過了，那麼n可能是質數，返回True。