什么是欧拉筛？？

欧拉筛（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 以内的所有素数，并打印结果。