与 "optimized" 迭代素数搜索相比，为什么埃拉托色尼筛法这么慢？ (Python 3)

Question

我尝试了一些不同版本的 Sieve，包括我自己的和来自不同页面的。不过，它们都有一个共同点。它们比我正在使用的迭代方法慢，这与我读过的关于 it.Is 的所有内容相悖，或者这是因为 python 列表处理速度慢？

from time import time
from random import randint

def isPrime(n):
    if (n <= 3):
        return (n >= 2)
    i = 5
    if (n % 2 == 0 or n % 3 == 0) :
        return False
    for i in range(5, int(n**.5)+1, 6):
        if (n%i == 0 or n%(i+2) == 0):
            return False
    return True

def sieveOfEratosthenes(n):
    array = [True for i in range((n-1)//2)]
    i = 3
    for e in array:
        if e is True:
            for k in range(i**2, n+1, 2*i):
                array[k//2-1] = False
        i += 2
    return [2]+[2*i+1 for i, e in enumerate(array, 1) if e is True]

def runIsPrime(arr):
    start = time()
    for e in arr:
        isPrime(e)
    print("Primes:\t\t", time()-start)

def runSieveOfEratosthenes(arr):
    start = time()
    primes = sieveOfEratosthenes(max(arr))
    #print("Sie. mid.:\t", time() - start)
    for e in arr:
        e in primes
    print("Sieve tot.:\t", time()-start)

upto = 10**6
times = 10**3
arr = [randint(2, upto) for i in range(times)]

runIsPrime(arr)
runSieveOfEratosthenes(arr)

给出打印输出：

Primes:      0.0019884109497070312 
Sieve tot.:  1.1940925121307373

Answer 1

您的 sieveOfEratosthenes 函数 returns 一个列表，并检查一个值是否在列表中 O(n)。但是，即使在将代码更改为使用 set 之后，筛子也会比您的直接方法慢：

def runSieveOfEratosthenes(arr):
    start = time()
    primes = set(sieveOfEratosthenes(max(arr)))
    #print("Sie. mid.:\t", time() - start)
    for e in arr:
        e in primes
    print("Sieve tot.:\t", time()-start)

upto = 10**6
times = 10**3
arr = [randint(2, upto) for i in range(times)]

runIsPrime(arr)
runSieveOfEratosthenes(arr)

输出：

Primes:      0.0013408660888671875
Sieve tot.:  0.19181394577026367

这是因为您的函数实际上在复杂性上有所不同。 isPrime 检查到根并提早退出，这使其可以快速处理小的复合数。 sieveOfEratosthenes 构建一个筛子，它是 O(n log log n) 并且它不依赖于列表的长度。让我们看看我们是否只传递更大尺寸的列表：

In [57]: ps = [996361] * 10**4

In [58]: runIsPrime(ps)
Primes:      0.20616984367370605

In [59]: runSieveOfEratosthenes(ps)
Sieve tot.:  0.1783740520477295

您可以看到，runIsPrime 性能急剧下降，而 runSieveOfEratosthenes 并没有太大变化。如果您认为这里可能涉及缓存，让我们准备不同素数的列表：

In [64]: ps2 = [x for x in range(10**5, 10**6) if isPrime(x)]

In [65]: len(ps2)
Out[65]: 68906

In [66]: ps2[-1]
Out[66]: 999983

In [67]: runIsPrime(ps2)
Primes:      0.9789869785308838

In [68]: runSieveOfEratosthenes(ps2)
Sieve tot.:  0.18288207054138184

如您所见，runIsPrime 执行时间随着数组长度的增加而增加，而 runSieveOfEratosthenes 时间大致保持不变。让我们进一步增加数组大小：

In [69]: runIsPrime(ps2 * 10)
Primes:      9.91222095489502

In [70]: runSieveOfEratosthenes(ps2 * 10)
Sieve tot.:  0.2231128215789795

作为结论 - 如果您需要检查一个数字是否为质数，您可以迭代到数字的根 - 这比构建筛子更快。如果你有一个数字列表，你可能想要运行一些测试，如果列表很小，你仍然可以使用第一种方法。但是当你有大量数字要检查时，最好构建一个筛子。

与 "optimized" 迭代素数搜索相比，为什么埃拉托色尼筛法这么慢？ (Python 3)

Why is Sieve of Eratosthenes so slow compared to "optimized" iterated prime search? (Python 3)

python

primes

sieve-of-eratosthenes