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

118次閱讀

共計(jì) 774 個(gè)字符，預(yù)計(jì)需要花費(fèi) 2 分鐘才能閱讀完成。

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

簡單的方法是遍歷從 2 到 n - 1 的所有整數(shù)，判斷 n 是否能被這些整數(shù)整除。如果 n 能被任何一個(gè)整數(shù)整除，則 n 不是質(zhì)數(shù)。這種方法的時(shí)間復(fù)雜度為 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

優(yōu)化的方法是只需要遍歷從 2 到 n 的平方根的整數(shù)即可。因?yàn)槿绻?n 能被大于其平方根的整數(shù)整除，那么一定能被小于其平方根的整數(shù)整除。同樣，如果 n 不能被小于其平方根的整數(shù)整除，那么一定不能被大于其平方根的整數(shù)整除。時(shí)間復(fù)雜度為 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

Sieve of Eratosthenes（埃拉托色尼篩選法）是一種篩選法，用于找出一定范圍內(nèi)的所有質(zhì)數(shù)。具體步驟是從 2 開始，將所有能被 2 整除的數(shù)標(biāo)記為非質(zhì)數(shù)，然后找到下一個(gè)未被標(biāo)記的數(shù)，將其作為質(zhì)數(shù)，并將其倍數(shù)標(biāo)記為非質(zhì)數(shù)，重復(fù)這個(gè)過程直到所有數(shù)都被標(biāo)記。時(shí)間復(fù)雜度為 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