超出Python中列表的大小限制

Question

我正在尝试用Python实现埃拉托斯特尼筛法，但是当我试图找出比如说779695003923747564589111193840021这个数的平方根以内的所有质数时，出现了一个错误，提示说range()的结果项数太多。我的问题是，怎么才能避免这个问题？如果我用while循环来创建列表，我会收到一个错误，提示我使用的内存太多（甚至在开始使用页面文件之前就出现了）。下面是这两种方法：

使用range()

maxnum = 39312312323123123

primes = []
seq = []
i = 0
seq = range(2,maxnum)

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

使用while：

maxnum = 39312312323123123

primes = []
seq = []
i = 0
while i < maxnum:
    seq.append(i)
    i+=1

for i in seq:
    mul = i * seq
    for j in mul:
        try:
            seq.remove(j)
        except:
            pass
        primes.append(i)

print primes

Answer 1

你的算法有问题。先让它在最大数字为100的情况下能正常运行。

一旦你让它能运行了，你会发现当最大数字是100000000时，运行会花费很长时间。

可以记录一下在不同最大数字（比如10、100、1000、10000、100000、1000000等）下运行所需的时间，这样你可能就能推测出39312312323123123需要多长时间才能运行 :)

Answer 2

我想说，“用 xrange() 来代替”，但你实际上是把整数列表当作筛选结果来用……所以用整数生成器并不是一个正确的解决方案。

我觉得无论你用什么方法，想要生成一个包含39312312323123123个元素的列表都是很困难的……毕竟，那是279个PB（拍字节）的64位整数。

试试这个。

class FoundComposite(Exception): pass

primes = [2]

seq = itertools.takewhile(        # Take integers from a list
          lambda x: x<MAXNUM,     #   until we reach MAXNUM
          itertools.count(2)      #   the list of integers starting from 2
          )

#seq = xrange(2, MAXNUM)          # alternatively

for i in seq:
    try:
        for divisor in primes:
            if not (i % divisor):
                # no remainder - thus an even divisor
                # continue to next i in seq
                raise FoundComposite 
        # if this is reached, we have tried all divisors.
        primes.append(i)
    except FoundComposite:
        pass

Answer 3

这是一个比较复杂的算法，可能从技术上来说不算是筛法，但有一种方法是，不一次性去掉所有某个质数的倍数，而是把下一个倍数和这个质数一起放到一个队列里。这种方法可以用在生成器的实现中。虽然队列里还是会有很多质数的倍数，但比起先建立一个列表再过滤掉多余的，数量会少一些。

下面是手动演示的前几个步骤，以展示这个原理……

• 2是质数 - 输出并把(4, 2)放入队列
• 3是质数 - 输出并把(6, 3)放入队列
• 4是合数 - 把队列中的(4, 2)替换成(6, 2)
• 5是质数 - 输出并把(10, 5)放入队列
• 6是合数 - 把(6, 2)替换成(8, 2)，把(6, 3)替换成(9, 3)

注意：这个队列不是先进先出（FIFO）的。你总是会提取第一个元素最小的元组，但新加的或替换的元组通常不会有最大的第一个元素（就像上面的6那样），所以会有重复的情况。

为了在Python中高效地处理这个队列，我建议使用一个字典（也就是哈希表），用元组的第一个元素作为键，数据则是第二个元素的值（原始质数）的集合。

正如其他地方所建议的，先用小的目标进行测试，再尝试大的目标。如果失败了也不要太惊讶。可能是你需要在队列中同时处理太多堆分配的大整数，导致无法完成解决方案。