Python中有效的Eratosthenes筛 [英] An Efficient Sieve of Eratosthenes in Python

问题描述

#Python中的这段非常简短的代码试图针对前N个自然数模拟"Eratosthenes筛"，其约束为(0)脚本简短； (1)最小化"if语句"和"for/while循环"； (2)就CPU时间而言的效率.

This very short and simple code in #Python tries to simulate the "Sieve of Eratosthenes" for the first N natural numbers with the constraints of (0) script shortness; (1) minimization of the 'if statements' and 'for/while loops'; (2) efficiency in terms of CPU time.

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上，它返回第一个中的质数:

On an Intel Core I5, it returns the prime numbers among the first:

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

• N = 100,000 in 0.03 seconds;
• N = 1,000,000 in 0.63 seconds;
• N = 10,000,000 in 22.2 seconds.

在上述限制内，有人愿意在CPU时间上共享更有效的代码吗?

Would someone like to share more efficient codes in term of CPU time within the aforementioned constraints?

推荐答案

一个Eratosthenes的 actual NumPy筛子看起来像这样:

An actual NumPy sieve of Eratosthenes looks like this:

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)

它维护一个可能为素数"标志的数组，并直接取消设置与素数倍数相对应的标志，而无需测试可除性，尤其是对于那些不能被当前正在处理的素数整除的数字.

It maintains an array of "possibly prime" flags and directly unsets the flags corresponding to multiples of primes, without needing to test divisibility, especially for numbers that aren't divisible by the prime currently being handled.

您正在做的是试法除法，即您只需要测试一下数字是否可以被候选除数整除.即便是良好的试验分工实施，也需要比筛分更多的操作和更昂贵的操作.您的实现所要做的工作甚至更多，因为它考虑了非素数候选除数，并且因为它一直在对其本应知道是质数的数字执行除数测试.

What you're doing is trial division, where you just go through and test whether numbers are divisible by candidate divisors. Even a good implementation of trial division needs to do more operations, and more expensive operations, than a sieve. Your implementation does even more work than that, because it considers non-prime candidate divisors, and because it keeps performing divisibility tests for numbers it should already know are prime.

这篇关于Python中有效的Eratosthenes筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！