python筛法求素数

Python中筛选素数的一个常见算法叫做埃拉托斯特尼筛法（Sieve of Eratosthenes），这是一种简单而高效的查找一定范围内所有质数的经典算法。以下是使用该方法编写的基本步骤：

def sieve_of_eratosthenes(n):
    primes = [True] * (n + 1)  # 创建一个布尔列表，初始全部设为True
    p = 2  # 首个质数
    while p * p <= n:
        # 如果primes[p]还没被标记为False，则它是个质数
        if primes[p]:
            for i in range(p * p, n + 1, p):  # 将p的倍数标记为非质数
                primes[i] = False
        p += 1  # 移动到下一个未检查的数

    # 返回所有大于等于2且标记为质数的索引对应的数字
    return [i for i in range(2, n + 1) if primes[i]]

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

这个函数首先假设从2到n的所有数字都是质数，然后从第一个质数2开始，将它的倍数标记为非质数。接下来找到下一个未被标记的数（即下一个质数），继续这个过程，直到遍历到平方根以上的数，因为之后的数如果有质因子已经被之前的质数处理过了。