什么是欧拉筛？？_python欧拉筛

欧拉筛（Euler's Sieve），又称线性筛法或欧拉线性筛，是一种高效筛选素数的方法。它的核心思想是从小到大遍历每个数，同时标记其倍数为合数，但每个合数只被其最小的质因数标记一次，从而避免了重复标记，实现了线性时间复杂度的素数筛选。

以下是一个使用 Python 实现的欧拉筛的例子：

def euler_sieve(n):  
    # 初始化标记数组，默认所有数都是素数（未标记）  
    is_prime = [True] * (n + 1)  
    is_prime[0] = is_prime[1] = False  
    primes = []  # 用于存储素数  
  
    for i in range(2, n + 1):  
        if is_prime[i]:  
            # i 是素数，将其加入素数列表  
            primes.append(i)  
            # 标记 i 的倍数为合数  
            for j in range(i * i, n + 1, i):  
                is_prime[j] = False  
  
    return primes  
  
# 示例：找出 100 以内的素数  
primes_up_to_100 = euler_sieve(100)  
print(primes_up_to_100)
'
运行
运行

在这段代码中，euler_sieve 函数接受一个整数 n 作为参数，返回小于等于 n 的所有素数的列表。函数内部首先创建了一个布尔数组 is_prime，用于标记每个数是否为素数。然后，函数从 2 开始遍历到 n，对于每个遍历到的数 i，如果 is_prime[i] 为真，则将 i 加入到素数列表中，并标记 i 的所有倍数为合数（从 i * i 开始，因为比 i 小的数的倍数已经被之前的素数标记过了）。

最终，函数返回素数列表。在这个例子中，我们调用 euler_sieve(100) 来找出 100 以内的所有素数，并打印结果。