python判斷素?cái)?shù)的方法有哪些

判斷一個(gè)數(shù)是否為素?cái)?shù)的方法有以下幾種：

1. 暴力法：對(duì)于每個(gè)大于1且小于該數(shù)的整數(shù)，判斷該整數(shù)能否整除該數(shù)。如果存在能整除的整數(shù)，則該數(shù)不是素?cái)?shù)；否則，該數(shù)是素?cái)?shù)。這種方法的時(shí)間復(fù)雜度是O(n)。

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

2. 優(yōu)化暴力法：在判斷能否整除時(shí)，可以只判斷小于等于√n的整數(shù)。因?yàn)槿绻嬖诖笥凇蘮的整數(shù)能整除n，那么一定存在小于√n的整數(shù)能整除n。這種方法的時(shí)間復(fù)雜度是O(√n)。

import math

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

3. Sieve of Eratosthenes（埃拉托斯特尼篩法）：先假設(shè)所有數(shù)都是素?cái)?shù)，然后從2開始，將所有2的倍數(shù)標(biāo)記為合數(shù)，再?gòu)?開始，將所有3的倍數(shù)標(biāo)記為合數(shù)，以此類推，直到√n。標(biāo)記完成后，剩下未被標(biāo)記的數(shù)即為素?cái)?shù)。這種方法的時(shí)間復(fù)雜度是O(nloglogn)。

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

以上是一些常用的判斷素?cái)?shù)的方法，不同方法的效率不同，可以根據(jù)具體需求選擇合適的方法。