埃氏筛法python

埃氏筛法（Sieve of Eratosthenes）是一种用于找出一定范围内所有素数的算法。它的基本思想是从2开始，将每个素数的倍数标记为合数，直到遍历完所有小于给定范围的数。以下是埃氏筛法的Python实现：

def sieve_of_eratosthenes(n):
    # 创建一个长度为n+1的布尔数组，用于标记数字是否为素数
    is_prime = [True] * (n + 1)
    is_prime = is_prime = False  # 0和1不是素数

    # 从2开始遍历到根号n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            # 将i的倍数标记为合数
            for j in range(i * i, n + 1, i):
                is_prime[j] = False

    # 收集所有素数
    primes = [i for i in range(n + 1) if is_prime[i]]
    return primes

使用示例：

n = 100
primes = sieve_of_eratosthenes(n)
print(primes)

这段代码将输出小于等于100的所有素数。