python筛选法求素数

Python代码：

def sieve_of_eratosthenes(n):
    """
    运用筛选法求出小于等于n的所有素数
    """
    # 初始化标记数组
    prime_flags = [True] * (n+1)
    # 首先排除0和1
    prime_flags[0] = prime_flags[1] = False
    # 从2开始筛选
    for i in range(2, int(n**0.5)+1):
        if prime_flags[i]:
            # 如果i是素数，则将i的倍数标记为合数
            for j in range(i**2, n+1, i):
                prime_flags[j] = False
    # 将标记为素数的数存入列表中
    primes = [i for i in range(2, n+1) if prime_flags[i]]
    return primes

函数`sieve_of_eratosthenes(n)`运用筛选法求出小于等于n的所有素数，并将它们存入一个列表中并返回。

筛选法的思路是先生成一个标记数组，将所有数标记为素数。然后从2开始，一个一个地筛选。对于每个素数i，将i的倍数标记为合数，直到大于n。最后，剩下的素数即为所有小于等于n的素数。

时间复杂度：$O(n\log\log n)$（因为 $1\times2,1\times 3,\ldots,1\times n$共有 $n-1$ 个数要判断，$2\times2,2\times3,\ldots,$同理；而 $k\times k$ 开始所有倍数均已经在 $2\times k,3\times k,\ldots,(n/k)\times k$ 中判断过了，为避免重复判定，在 $k>\sqrt n$ 时直接跳过。）