2

我正在尝试实施埃拉托色尼筛法。输出似乎是正确的（减去需要添加的“2”），但如果函数的输入大于 100k 左右，它似乎需要过多的时间。我可以通过哪些方式优化此功能？

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
4

6 回答 6

1

您的算法不是埃拉托色尼筛法。您执行试除法（模数运算符）而不是像埃拉托色尼在两千多年前所做的那样交叉倍数。这是对真正筛选算法的解释，下面显示的是我的简单、直接的实现，它返回一个不超过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, ... 之间。

您可以在http://ideone.com/YTaMB看到这个函数的运行情况，它可以在不到一秒的时间内将质数计算为一百万。

于 2012-01-28T12:24:35.213 回答
0

你可以尝试像 Eratosthenes 一样的方法。取一个包含所有数字的数组，以检查升序，转到数字 2 并标记它。现在每隔一个数字刮一次，直到数组结束。然后转到3并标记它。之后每三号刮一次。然后转到 4 - 它已经被划伤了，所以跳过它。对尚未划伤的每个 n+1 重复此操作。

最后，标记的数字是质数。此算法速度更快，但有时需要大量内存。您可以通过删除所有偶数（因为它们不是素数）并手动将 2 添加到列表中来对其进行一些优化。这会稍微扭曲逻辑，但会占用一半的内存。

这是我在说什么的一个例子：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

于 2012-01-28T08:06:42.547 回答
0

警告：在迭代时从迭代器中删除元素可能是危险的......

你可以使

    if(thing % divisor == 0) and thing != divisor:

通过将其拆分到当您到达“除数”索引然后测试时中断的循环中来测试打火机： 

for thing in numberList_fromDivisorOn:
    if(thing % divisor == 0):
        numberList.remove(thing)
于 2012-01-28T08:12:16.313 回答
0

我点击了这个链接：Sieve of Eratosthenes - Finding Primes Python asSuggested by @MAK 并且我发现可以通过我在您的代码中找到的想法来改进接受的答案：

def primes_sieve2(limit):
    a = [True] * limit               # Initialize the primality list
    a[0] = a[1] = False
    sqrt = int(math.sqrt(limit))+1
    for i in xrange(sqrt):
        isprime = a[i]
        if isprime:
            yield i
            for n in xrange(i*i, limit, i):     # Mark factors non-prime
                a[n] = False
    for (i, isprime) in enumerate(a[sqrt:]):
        if isprime:
            yield i+sqrt
于 2012-01-28T08:39:36.717 回答
0

如果给定无限的内存和时间，以下代码将打印所有素数。它会在不使用试用部门的情况下完成。它基于论文中的 Haskell 代码：Melissa E. O'Neill 的 The Genuine Sieve of Eratosthenes

from heapq import heappush, heappop, heapreplace
def sieve():
    w = [2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10]
    for p in [2,3,5,7]: print p
    n,o = 11,0
    t = []
    l = len(w)
    p = n
    heappush(t, (p*p, n,o,p))
    print p
    while True:
        n,o = n+w[o],(o+1)%l
        p = n
        if not t[0][0] <= p:
            heappush(t, (p*p, n,o,p))
            print p
            continue
        while t[0][0] <= p:
            _, b,c,d = t[0]
            b,c = b+w[c],(c+1)%l
            heapreplace(t, (b*d, b,c,d))
sieve()
于 2012-01-28T10:17:06.817 回答
0

这段代码需要 2 秒来生成小于 10M 的素数（这不是我的，我在 google 上发现了一些）

def erat_sieve(bound):
    if bound < 2:
        return []
    max_ndx = (bound - 1) // 2
    sieve = [True] * (max_ndx + 1)
    #loop up to square root
    for ndx in range(int(bound ** 0.5) // 2):
        # check for prime
        if sieve[ndx]:
            # unmark all odd multiples of the prime
            num = ndx * 2 + 3
            sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
    # translate into numbers
    return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]
于 2012-01-28T12:57:04.930 回答