Eratosthenes 实施的慢筛法。为什么？

Question

我想将 Eratosthenes 筛法实现到它的基本水平，而不对检查平方根或类似的东西进行优化。

我不明白为什么这个实现这么慢... 运行筛选 10^5 大约需要 110 秒，这比类似的实现慢得多。

有人能解释一下罪魁祸首在哪里吗？

def sieve(n, out = True):
    start_time = time.time()
    isPrime = [True] * (n-1) # (n-1) since we do not include 0 or 1
    p = 2

    while True:
        multiplier = 2
        multiple = p*multiplier
        # mark all multiples of p as False
        while multiple <= n:
            isPrime[multiple-2] = False # subtract 2 since the list starts at 2. Hence indices and numbers are shifted by 2
            multiplier +=1
            multiple = p*multiplier
        # change p to next prime
        for i, prime in enumerate(isPrime):
            if prime and i+2>p: #remember indices are off by 2 
                p = i+2
                break
        else:
            break
    end_time = time.time()
    if out:
        for i, prime in enumerate(isPrime):
            if prime:
                print(i+2)

    print("Computation took: %0.05f" % (end_time- start_time))

Answer 1

你做的工作比必要的多。你在筛分的时候把加法转乘法，筛分的起点和终点都比需要的大。这是我的实现，它解决了这些问题并将 2 作为特殊情况处理：

def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p <= n:
        if sieve[i]:
            ps.append(p)
            for j in range((p*p-3)/2, m, p):
                sieve[j] = False
        i, p = i+1, p+2
    return ps

Answer 2

只需简化代码，它就会运行得很快：

from time import time
def sieve(n, out = True):
    start_time = time()
    isPrime = [True] * (n + 1) 

    for p in range(2, n + 1):
        for multiple in range(p * 2, n + 1, p):
            isPrime[multiple] = False

    end_time = time()
    if out:
        for i, prime in enumerate(isPrime):
            if prime and i > 1:
                print(i)

    print("Computation took: %0.05f" % (end_time- start_time))

计算耗时：0.09900 秒

Eratosthenes 实施的慢筛法。为什么？

Slow Sieve of Eratosthenes implementation. Why?

python

optimization

primes

sieve-of-eratosthenes