为什么我的桑达拉姆筛法如此低效

Question

我最近在研究质数筛选算法的性能，尝试了一个叫做Sundaram筛的算法。我的代码实现如下：

import time
from pympler import asizeof

start = time.perf_counter()
limit = 10000
upper = int(limit/2)
numbers = [i for i in range(upper)]

for j in range(1,int(upper/2)):
    i = 1
    while i <= j:
        n = i + j + (2*i*j)
        if n in numbers and n < upper:
            numbers[numbers.index(n)] = 0
        i += 1

primes = [2, 3]
for number in numbers:
    if number != 0:
        primes.append(number*2 + 1)

stop = time.perf_counter()
print(primes)
print(f'Time = {stop - start} sec')
print(f'List of numbers: {asizeof.asizeof(numbers)}')
print(f'List of primes: {asizeof.asizeof(primes)}') 

运行结果显示：

• 找出100以下的质数：0.0002秒
• 找出1000以下的质数：0.0772秒
• 找出10000以下的质数：97.71秒
• 找出100000以下的质数：超过30分钟（我最后终止了这个过程）

我觉得这个算法本身并没有问题，因为我实现的其他算法运行得比这个快得多，所以问题可能出在我的代码上。我的代码中哪个部分导致了这么长的运行时间呢？

Answer 1

你不需要执行 n in numbers 这个操作。也不用调用 index 来找索引，因为索引就是 n。只要检查一下 n 是否在范围内，然后把 numbers[n] 设置为零，即使它已经是零也没关系。

除此之外，还有一些地方可以改进：

• 不要明确加3，因为最后的循环已经加了。
• 当你需要整数除法时，不要用浮点数除法（用 //）。
• 每次循环时不要从 i 等于1开始。你可以从 j 开始，然后处理 i >= j 的范围（这就是 维基百科上说的）。
• 当 n 超出范围时，不要继续循环。这可以作为你循环的退出条件。

这里是需要修正的部分：

upper = limit // 2  # use integer division
numbers = list(range(upper))

for j in range(1, upper//2):
    i = j  # Deal with the range from j onwards (until n exceeds)
    while True:
        n = i + j + 2 * i * j
        # No need to check membership in numbers
        if n >= upper:  # This is an exit condition. No need to continue
            break
        numbers[n] = 0
        i += 1
# Don't add 3 explicitly, as it will be added by the loop
# Use comprehension:
primes = [2] + [number*2 + 1 for number in numbers if number]