超过python中列表的大小

Question

我正在尝试在python中实现eratosthenes的筛子,但是当试图找到所有素数达到sqare根时,例如779695003923747564589111193840021我得到一个错误,说range()的结果有太多的项目.我的问题是,我如何避免这个问题,如果我用while循环实例化列表,我会得到一个错误,说我使用了太多的内存(在它开始使用页面文件之前),下面列出了两个:

使用范围()

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

我会说," 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