素数筛

暴力法

时间复杂度: $O(n^2)$
内层的 $is\_prime()$ 函数使用遍历查找，其平均时间复杂度为 $O(\frac{n}{2})$，$sieve()$ 函数同样使用遍历查找，时间复杂度显然为 $O(n)$，对于该算法的循环结构，平均时间复杂度为 $O(\frac{n^2}{2}) = O(n^2)$

def is_prime(num):
    if num < 2:  # 直接排除
        return False
    for i in range(2, num): # 遍历
        if num % i == 0:
            return False
    return True

def sieve(n):
    primes = []
    for i in range(2, n + 1):
        if is_prime(i):
            primes.append(i)
    return primes

$O(n\sqrt{n})$

时间复杂度： $O(n\sqrt{n})$
内层的 $is\_prime()$ 函数使用有剪枝的遍历查找，其平均时间复杂度为 $O(\frac{\sqrt{n}}{2})$，$sieve()$ 函数同样使用遍历查找，时间复杂度显然为 $O(n)$，对于该算法的循环结构，平均时间复杂度为 $O(\frac{n\sqrt{n}}{2}) = O(n^2)$

import math

def is_prime(num):
    if num < 2:
        return False
    # 非素数至少有一个小于等于 sqrt(n) 的因数，如果没有，显然也不存在大于1的因数，直接剪枝
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def sieve(n):
    primes = []
    for i in range(2, n + 1):
        if is_prime_optimized(i):
            primes.append(i)
    return primes

调和级数法

时间复杂度: $O(n\log{n})$
内层的 $for$ 循环使用有剪枝的遍历查找，由于使用了已有素数实现了调和级数，其平均时间复杂度为 $O(\log{n})$，外层for循环使用直接遍历查找，时间复杂度显然为 $O(n)$，对于该算法的循环结构，平均时间复杂度为 $O(n\log{n})$。

def sieve_harmonic(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for prime in primes:
            if prime * prime > num:  # 剪枝
                break
            # 利用已有素数进行校验
            if num % prime == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

埃氏筛

时间复杂度: $O(n\log{\log{n}})$

def sieve(n):
    is_prime = [True] * (n + 1)
    p = 2
    while (p * p <= n):
        if is_prime[p]:
            for i in range(p * p, n + 1, p):
                is_prime[i] = False
        p += 1
    primes = [p for p in range(2, n + 1) if is_prime[p]]
    return primes

线性筛

时间复杂度: $O(n)$
线性筛通过优化埃氏筛，避免了重复标记非素数，因为每一个数只查询有限次，所以复杂度为线性，算法时间复杂度为 $O(n)$

def sieve(n):
    is_prime = [True] * (n + 1)
    primes = []
    for p in range(2, n + 1):
        if is_prime[p]:
            primes.append(p)
        for prime in primes:
            if p * prime > n:
                break
            is_prime[p * prime] = False
            if p % prime == 0:
                break
    return primes