Prime-Nummer Generator stürzt ab Speicherfehler, wenn es zu viele Zahlen in Array

Question

Ich habe eine Primzahl-Generator, war ich neugierig zu sehen, wie klein und wie schnell könnte ich einen Primzahl-Generator auf Optimierungen basieren und solche:

from math import sqrt 
def p(n): 
    if n < 2: return [] 
    s = [True]*(((n/2)-1+n%2)+1) 
    for i in range(int(sqrt(n)) >> 1): 
    if not s[i]: continue 
    for j in range((i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False 
    q = [2]; q.extend([(i<<1) + 3 for i in range(((n/2)-1+n%2)) if s[i]]); return len(q), q 
print p(input()) 

Der Generator funktioniert gut! Es ist super schnell, fühlen Sie sich frei, es auszuprobieren. Wenn Sie jedoch Zahlen größer als 10^9 oder 10^10 eingeben (denke ich), wird es von einem Speicherfehler abstürzen. Ich kann nicht herausfinden, wie ich den Speicher erweitern kann, damit er so viel wie nötig braucht. Jeder Rat würde sehr geschätzt werden!

Meine Frage ist sehr ähnlich this ein, aber das ist Python, nicht C.

EDIT: Dies ist eine der speicherbezogenen Tracebacks ich für den Versuch, bekommen 10^9 zu laufen.

python prime.py 
1000000000 
Traceback (most recent call last): 
    File "prime.py", line 9, in <module> 
    print p(input()) 
    File "prime.py", line 7, in p 
    for j in range((i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False 
MemoryError 

Answer 1

Das Problem ist in Zeile 7.

for j in range((i**i+(3*i) << 1) + 3, ((n/2)-1+n%2), (i<<1)+3): s[j] = False 

insbesondere dieser Teil: i**i

1000000000^1000000000 ist ein 9 * 10^9-stellige Zahl lange. Die Speicherung dauert mehrere Gb, wenn nicht Tb (WolframAlpha konnte es nicht mehr nachweisen). Ich weiß, dass i die Quadratwurzel von n (maximal) ist, aber bei diesen großen Zahlen ist das kein großer Unterschied.

Sie müssen diese Komponente in kleinere Teile aufteilen, wenn es möglich ist, und auf einer Festplatte sichern. Dies macht den Prozess langsam, aber machbar.

Answer 2

Zuerst gibt es ein Problem, da der Generator sagt, dass Zahlen wie 33, 35 und 45 Primzahl sind.

Abgesehen davon, gibt es mehrere Strukturen hier Speicher Aufnahme:

• s = [True]*(((n/2)-1+n%2)+1)

Ein Listenelement mehrere Bytes pro Element in Anspruch nimmt. Für n = 1 Milliarde benötigt das Array s Gigabytes.

range(...) erstellt eine Liste und iteriert dann über die Elemente. Verwenden Sie stattdessen xrange(...) wo möglich.

Konvertieren von range() zu xrange() hat Fallstricke - z.B. siehe das so beantworten:

OverflowError Python int too large to convert to C long

Eine bessere Umsetzung der s ist eine ganze Zahl Python als Bit-Array zu verwenden, die eine Dichte von 8 Elementen pro Byte hat. Hier ist eine Übersetzung zwischen einer Liste mit und einer ganzen Zahl:

s = [True]*(((n/2)-1+n%2)+1)  t = (1 << (n/2)+1)-1 

s[i]        (t & (1<<i)) 
not s[i]       not (t & (1<<i)) 

s[j] = False      m = 1<<j 
            if (t & m): t ^= m 

aktualisiert

Hier ist eine nicht optimierte Version, die yield und xrange verwendet.Bei größeren Werten von n sind die oben genannten Einschränkungen von xrange zu beachten.

def primes(n): 
    if n < 2: return 
    yield 2 
    end = int(sqrt(n)) 
    t = (1 << n) -1 

    for p in xrange(3, end, 2): 
    if not (t & (1 << p)): continue 
    yield p 
    for q in xrange(p*p, n, p): 
     m = t & (1<<q) 
     if (t&m): t ^= m 
     continue 

    for p in xrange(end - (end%2) +1, n, 2): 
    if not (t & (1 << p)): continue 
    yield p 


def test(n): 
    for p in primes(n): print p 

test(100000)