python 用筛法求素数

在Python中，我们可以使用埃拉托斯特尼筛法（Sieve of Eratosthenes）来求解一定范围内的所有素数。这是一种古老的算法，通过不断地排除合数来找出剩余的素数。以下是实现该算法的一个基本步骤：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 初始化一个布尔数组，表示0到n的每个数是否是素数，默认认为都是
    primes[0], primes[1] = False, False  # 0和1不是素数

    for i in range(2, int(n**0.5) + 1):  # 只需要检查到n的平方根，因为大于这个数的因子必然有一个小于它本身
        if primes[i]:  # 如果i是素数
            for j in range(i*i, n + 1, i):  # 将i的倍数标记为非素数
                primes[j] = False

    # 返回索引对应的值就是素数，列表形式更直观
    return [i for i, is_prime in enumerate(primes) if is_prime]

# 示例
n = 30
print(sieve_of_eratosthenes(n))  # 输出：[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

在这个函数中，我们首先创建了一个布尔数组`primes`，然后从2开始，将它的倍数标记为非素数。当遍历完2到√n的所有数后，剩下的未被标记的数即为素数。