python判斷質數(shù)的方法有哪些

判斷質數(shù)的方法有以下幾種：

1. 簡單的方法是遍歷從2到n-1的所有整數(shù)，判斷n是否能被這些整數(shù)整除。如果n能被任何一個整數(shù)整除，則n不是質數(shù)。這種方法的時間復雜度為O(n)。

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

2. 優(yōu)化的方法是只需要遍歷從2到n的平方根的整數(shù)即可。因為如果n能被大于其平方根的整數(shù)整除，那么一定能被小于其平方根的整數(shù)整除。同樣，如果n不能被小于其平方根的整數(shù)整除，那么一定不能被大于其平方根的整數(shù)整除。時間復雜度為O(sqrt(n))。

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

3. Sieve of Eratosthenes（埃拉托色尼篩選法）是一種篩選法，用于找出一定范圍內的所有質數(shù)。具體步驟是從2開始，將所有能被2整除的數(shù)標記為非質數(shù)，然后找到下一個未被標記的數(shù)，將其作為質數(shù)，并將其倍數(shù)標記為非質數(shù)，重復這個過程直到所有數(shù)都被標記。時間復雜度為O(nloglogn)。

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    p = 2
    while p * p <= n:
        if primes[p]:
            for i in range(p * p, n + 1, p):
                primes[i] = False
        p += 1
    return primes

這些方法可以根據(jù)具體情況選擇使用。如果只需要判斷一個數(shù)是否為質數(shù)，可以使用第一種或第二種方法。如果需要找出一定范圍內的所有質數(shù)，可以使用第三種方法。