python - Python 中埃拉托色尼的高效筛法

Question

#Python 中的这段非常简短的代码试图模拟前 N 个自然数的“Eratosthenes 筛法”，并具有 (0) 脚本短小的约束； (1) 最小化“if 语句”和“for/while 循环”； (2) CPU 时间方面的效率。

import numpy as np
N = 10**5
a = np.array(range(3,N,2))
for j in range(0, int(round(np.sqrt(N),0))):
    a[(a!=a[j]) & (a%a[j] == 0)] = 0
    a = a[a!=0]
a = [2]+list(a)

在 Intel Core I5 上，它返回前几个素数:

• N = 100,000 在 0.03 秒内；
• N = 1,000,000 在 0.63 秒内；
• N = 10,000,000 在 22.2 秒内。

在上述限制条件下，有人愿意分享在 CPU 时间方面更高效的代码吗？

Answer 1

Eratosthenes 的实际 NumPy 筛法如下所示:

def sieve(n):
    flags = numpy.ones(n, dtype=bool)
    flags[0] = flags[1] = False
    for i in range(2, n):
        # We could use a lower upper bound for this loop, but I don't want to bother with
        # getting the rounding right on the sqrt handling.
        if flags[i]:
            flags[i*i::i] = False
    return numpy.flatnonzero(flags)

它维护一个“可能是素数”标志的数组，并直接取消设置与素数倍数对应的标志，而不需要测试整除性，特别是对于不能被当前正在处理的素数整除的数字。

您正在做的是试验除法，您只需检查并测试数字是否可以被候选除数整除。即使是一个很好的 trial division 实现也需要比筛子做更多的操作，而且操作成本更高。您的实现所做的工作甚至比这更多，因为它考虑了非素数候选除数，并且因为它不断对应该已经知道是素数的数字执行可除性测试。