← 都来码 / Dolaima← 例程索引python/school/sieve_of_eratosthenes.py 原文

python/school/sieve_of_eratosthenes.py · 309 字节 · 下载原文

def primes_upto(limit):
    is_prime = [False] * 2 + [True] * (limit - 1) 
    for n in range(int(limit**0.5 + 1.5)): # stop at ``sqrt(limit)``
        if is_prime[n]:
            for i in range(n*n, limit+1, n):
                is_prime[i] = False
    return [i for i, prime in enumerate(is_prime) if prime]