埃氏筛法与欧拉筛python

埃氏筛法：

def Eratosthenes(n):
    primes = [True] * (n + 1)
    primes[0], primes[1] = False, False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            primes[i * i: n + 1: i] = [False] * len(primes[i * i: n + 1: i])
    return [i for i in range(n + 1) if primes[i]]

欧拉筛：

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

两者的时间复杂度都是 $O(n \log \log n)$，但在常数上欧拉筛比埃氏筛法小，因此欧拉筛法更快。