python质数求法

在Python中，可以使用以下几种方法来求解质数：

1. 基本方法：遍历从2到n-1的所有数字，判断是否能整除n。如果存在能整除n的数字，则n不是质数；否则，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. 优化方法：在基本方法的基础上，可以进行一些优化。例如，只需要遍历从2到sqrt(n)的数字即可，因为如果存在大于sqrt(n)的因子，那么一定存在小于sqrt(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（埃拉托斯特尼筛法）：该方法通过不断筛选出质数的倍数来找到所有质数。具体步骤如下：

- 创建一个长度为n+1的布尔数组is_prime，并将所有元素初始化为True。
- 将is_prime和is_prime设置为False，因为0和1不是质数。
- 从2开始遍历到sqrt(n)，对于每个素数p，将is_prime[p]设置为True，并将p的倍数is_prime[p*i]（i从2开始）设置为False。
- 遍历is_prime数组，将为True的索引值添加到结果列表中。

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 = [i for i in range(n + 1) if is_prime[i]]
    return primes

这些是Python中常用的几种质数求解方法。你可以根据具体需求选择合适的方法来使用。