python 素数筛选算法解析

素数筛法是一种用于查找素数的算法，其基本思路是从小到大依次枚举每一个数，如果该数还没有被标记为非素数，则将其所有的倍数都标记为非素数。最终没有被标记的数即为素数。

Python实现素数筛法通常有两种方式：埃氏筛和欧拉筛。

1. 埃氏筛法

埃氏筛法是一种最简单直观的素数筛法，其思想是从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的。

具体实现过程如下：

def eratosthenes(n):
    is_prime = [True] * (n+1)  # 先将所有数标记为素数
    is_prime[0] = is_prime = False  # 0和1不是素数
    for i in range(2, int(n**0.5)+1):  # 从2到根号n枚举每个质数
        if is_prime[i]:  # 如果i是素数
            for j in range(i*i, n+1, i):  # 将i的倍数都标记成合数
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]  # 返回所有素数的列表

2. 欧拉筛法

欧拉筛法是一种时间复杂度更优秀的素数筛法，其核心思想是在筛选过程中避免重复标记合数，通过每个合数只被它的最小质因子筛选一次来实现。

具体实现过程如下：

def euler(n):
    is_prime = [True] * (n+1)  # 先将所有数标记为素数
    prime = []  # 存储所有素数
    for i in range(2, n+1):  # 从2到n枚举每个数
        if is_prime[i]:  # 如果i是素数
            prime.append(i)  # 加入素数列表
        for p in prime:  # 遍历已有的素数
            if p * i > n:  # 如果已有的最大素数乘以i已经超过n，就不必再筛了
                break
            is_prime[p * i] = False  # 将p*i标记成合数
            if i % p == 0:  # 如果i能够整除p，说明p是i的最小质因子
                break
    return prime  # 返回所有素数的列表