python判断素数的方法有哪些

判断一个数是否为素数的方法有以下几种：

1. 暴力法：对于每个大于1且小于该数的整数，判断该整数能否整除该数。如果存在能整除的整数，则该数不是素数；否则，该数是素数。这种方法的时间复杂度是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. 优化暴力法：在判断能否整除时，可以只判断小于等于√n的整数。因为如果存在大于√n的整数能整除n，那么一定存在小于√n的整数能整除n。这种方法的时间复杂度是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（埃拉托斯特尼筛法）：先假设所有数都是素数，然后从2开始，将所有2的倍数标记为合数，再从3开始，将所有3的倍数标记为合数，以此类推，直到√n。标记完成后，剩下未被标记的数即为素数。这种方法的时间复杂度是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 

以上是一些常用的判断素数的方法，不同方法的效率不同，可以根据具体需求选择合适的方法。