Как решить эту ошибку памяти - 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()

Алгоритм генерации простых чисел взят из Simple Prime Generator в 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

Этот простой генератор не использует много памяти.Это тоже не очень быстро.

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

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

Я выполнил слегка измененный код на моей машине 10 ^ 6 простых чисел за ~ 30 с (я использую Python 3.2)

Вот код:

def gen_primes():  
    D = {}  
    # The running integer that's checked for primeness
    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


def main():
    j = 0
    f = open("primes1.txt","w")
    for i in gen_primes():
        j += 1
        #print(j, i)
        f.write(str(i) + "\n")
        if (j > 10000000): break
    f.close()

if __name__ == "__main__":
    main()

Answer 4

Попробуйте использовать этот генератор: 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()