如何解决这个内存错误 - python

Question

我有以下代码：

    def gen_primes():

        D = {}  

        q = 2  

        while True:
            if q not in D:         
                yield q        
                D[q * q] = [q]
            else:           
                for p in D[q]:
                    D.setdefault(p + q, []).append(p)
                del D[q]

            q += 1


    f = open("primes1.txt","w")

    filen = 1
    ran1 = 1
    ran2 = 10000000

    k = 1
    for i in gen_primes():

        if (k >= ran1) and (k <= ran2):

            f.write(str(i) + "\n")
            if k%1000000 == 0:
                print k
            k = k + 1
        else:
            ran1 = ran2 + 1
            ran2 = ran2 + 10000000
            f.close()
            filen = filen + 1;
            f = open("primes" + str(filen) + ".txt","w")

        if k > 100000000:           
            break
    f.close()

这个生成质数的算法来自于 Python中的简单质数生成器

这个程序出现了内存错误。

Traceback (most recent call last):
  File "C:\Python25\Projects\test.py", line 43, in <module>
    for i in gen_primes():
  File "C:\Python25\Projects\test.py", line 30, in gen_primes
    D.setdefault(p + q, []).append(p)
MemoryError

我想把连续的10,000,000个质数存储在一个文件里。

Answer 1

试试这个生成器：http://code.activestate.com/recipes/366178-a-fast-prime-number-list-generator/

它的速度非常快，可以在几秒钟内生成10000000个质数，而且占用的内存也不多。

如果你想把结果保存到文件里，可能直接用下面这种方式会更简单：

interval_start = 100
interval_length = 10000000
f = open("primes1.txt","w")

for prime in primes(interval_start + interval_length)[interval_start::]:
   f.write(str(prime) + "\n")

f.close()

Answer 2

安装这个叫做 gmpy 的软件包后，你就可以在写文件的时候几乎不需要占用太多内存了。

import gmpy
p=2
with open("primes.txt","w") as f:
    for n in xrange(100000000):
        print >> f, p
        p = gmpy.next_prime(p)

Answer 3

这个质数生成器占用的内存不多，但速度也不是很快。

def gcd(a, b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

def primegen():
    yield 2
    yield 3
    yield 5
    yield 7
    yield 11
    accum = 2*3*5*7
    out = file('tmp_primes.txt', 'w')
    inp = file('tmp_primes.txt', 'r+')
    out.write('0x2\n0x3\n0x5\n0x7\n0xb\n')
    inp.read(20)
    inpos = inp.tell()
    next_accum = 11
    next_square = 121
    testprime = 13
    while True:
        if gcd(accum, testprime) == 1:
            accum *= testprime # It's actually prime!
            out.writelines((hex(testprime), '\n'))
            yield testprime
        testprime += 2
        if testprime >= next_square:
            accum *= next_accum
            nextline = inp.readline()
            if (len(nextline) < 1) or (nextline[-1] != '\n'):
                out.flush()
                inp.seek(inpos)
                nextline = inp.readline()
            inpos = inp.tell()
            next_accum = int(nextline, 16)
            next_square = next_accum * next_accum

def next_n(iterator, n):
    """Returns the next n elements from an iterator.

    >>> list(next_n(iter([1,2,3,4,5,6]), 3))
    [1, 2, 3]
    >>> list(next_n(primegen(), 10))
    [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    """
    while n > 0:
        yield iterator.next()
        n -= 1