Python中Eratosthenes的高效筛选

Question

#Python中这个非常简短的代码试图模拟前N个自然数的"Sieve of 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上,它返回第一个中的素数:

• 在0.03秒内N = 100,000;
• 在0.63秒内N = 1,000,000;
• 在22.2秒内N = 10,000,000.

有人愿意在上述约束条件下分享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)

它维护一个"可能是素数"标志的数组,并直接取消对应于质数倍数的标志,而不需要测试可分性,特别是对于当前正在处理的素数不能整除的数字.

你正在做的是试验部门,在那里你只需要检查数字是否可以被候选除数整除.即使是试验部门的良好实施也需要做更多的操作,而且比筛子更昂贵的操作.你的实现确实比这更有用,因为它考虑了非素数候选除数,并且因为它不断对数字进行可分性测试,它应该已经知道是素数.