Python Eratosthenes筛选算法优化

问题描述

我正在尝试实施Eratosthenes筛网.输出似乎是正确的(需要加上负"2")，但是如果函数的输入大于100k左右，则似乎要花费过多的时间.我可以通过哪些方式优化此功能?

I'm attempting to implement the Sieve of Eratosthenes. The output seems to be correct (minus "2" that needs to be added) but if the input to the function is larger than 100k or so it seems to take an inordinate amount of time. What are ways that I can optimize this function?

def sieveErato(n):
     numberList = range(3,n,2)

     for item in range(int(math.sqrt(len(numberList)))):
            divisor = numberList[item]
            for thing in numberList:
                    if(thing % divisor == 0) and thing != divisor:
                            numberList.remove(thing)
    return numberList

推荐答案

您的算法不是Eratosthenes的筛网.您执行试验除法(模运算符)，而不是像两千多年前的Eratosthenes那样进行相乘. 此处是对真正的筛选算法的解释，如下所示:我简单，直接的实现，它返回不超过 n 的素数列表:

Your algorithm is not the Sieve of Eratosthenes. You perform trial division (the modulus operator) instead of crossing-off multiples, as Eratosthenes did over two thousand years ago. Here is an explanation of the true sieving algorithm, and shown below is my simple, straight forward implementation, which returns a list of primes not exceeding n:

def sieve(n):
    m = (n-1) // 2
    b = [True]*m
    i,p,ps = 0,3,[2]
    while p*p < n:
        if b[i]:
            ps.append(p)
            j = 2*i*i + 6*i + 3
            while j < m:
                b[j] = False
                j = j + 2*i + 3
        i+=1; p+=2
    while i < m:
        if b[i]:
            ps.append(p)
        i+=1; p+=2
    return ps

我们仅对奇数进行筛选，停在 n 的平方根处. j 映射上的奇数计算介于被筛分的3、5、7、9，...与 b中的索引0、1、2、3，...之间位数组.

We sieve only on the odd numbers, stopping at the square root of n. The odd-looking calculations on j map between the integers being sieved 3, 5, 7, 9, ... and indexes 0, 1, 2, 3, ... in the b array of bits.

您可以在 http://ideone.com/YTaMB 上看到此函数的运行情况，该函数在其中计算在不到一秒钟的时间内即可达到百万.

You can see this function in action at http://ideone.com/YTaMB, where it computes the primes to a million in less than a second.

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