prime Generator Optimierung

Question

Ich beginne meine Expedition ins Projekt Euler. Und wie viele andere habe ich gedacht, ich muss einen Primzahlengenerator machen. Problem ist: PHP mag keine großen Zahlen. Wenn ich den Standard Sieve of Eratosthenes function verwende und das Limit auf 2 Millionen setze, stürzt es ab. Es mag nicht, Arrays dieser Größe zu erstellen. Verständlich.

Also jetzt versuche ich es zu optimieren. Ein Weg, den ich fand, war, anstatt ein Array mit 2 Millionen Variablen zu erstellen, brauche ich nur 1 Million (nur ungerade Zahlen können Primzahlen sein). Aber jetzt stürzt es, weil sie die maximale Ausführungszeit überschreitet ...

function getPrimes($limit) { 
$count = 0; 
for ($i = 3; $i < $limit; $i += 2) { 
    $primes[$count++] = $i; 
} 

for ($n = 3; $n < $limit; $n += 2) { 
    //array will be half the size of $limit 
    for ($i = 1; $i < $limit/2; $i++) { 
     if ($primes[$i] % $n === 0 && $primes[$i] !== $n) { 
      $primes[$i] = 0; 
     } 
    } 
} 

return $primes; 
} 

Die Funktion arbeitet, aber wie gesagt, es ist ein bisschen langsam ... irgendwelche Vorschläge?

Eine Sache, die ich gefunden habe, um es ein bisschen schneller zu machen, ist, die Schleife herum zu schalten.

foreach ($primes as $value) { 
    //$limitSq is the sqrt of the limit, as that is as high as I have to go 
    for ($n = 3; $n = $limitSq; $n += 2) { 
     if ($value !== $n && $value % $n === 0) { 
      $primes[$count] = 0; 
      $n = $limitSq; //breaking the inner loop 
     } 
    } 
    $count++; 
} 

Und zusätzlich Zeit und Speicherlimit (Dank Greg), habe ich endlich eine Antwort bekommen. Phjew.

Answer 1

Von Algorithmist's proposed solution

Dies ist eine Modifikation des Standard Sieb des Eratosthenes. Es wäre sehr ineffizient, zu viel zu verwenden viel Speicher und Zeit, um das Standard-Sieb den ganzen Weg bis n laufen zu lassen. jedoch keine zusammengesetzte Zahl kleiner als oder gleich n wird einen Faktor größer als sqrt {n}, so müssen wir wissen, nur alle Primzahlen bis zu dieser Grenze, die nicht größer als 31622 (Quadratwurzel von 10^9). Diese wird mit einem Sieb durchgeführt. Dann, für jede Abfrage, wir Sieb durch nur der angegebenen Bereich, mit unserer vorberechnete Tabelle der Primzahlen zu eliminieren zusammengesetzte Zahlen.

Dieses Problem ist auch bei Online-Richtern von UVA und Sphere aufgetreten. Here's how it's enunciated on Sphere.

Answer 2

Ohne viel zu wissen über den Algorithmus:

1. Du neu berechnet $limit/2 jedes Mal um die i-Schleife $
2. Ihre if-Anweisung wird ausgewertet werden, um, so denken Sie an (oder Test), ob es wäre schneller zu testen $primes[$i] !== $n zuerst.

Randnotiz, können Sie set_time_limit() verwenden, um ihn mehr mehr Speicher zu laufen und geben Sie Ihr Setup mit

ini_set('memory_limit', '128M'); 

Unter der Annahme, ermöglicht dies, natürlich - auf einem gemeinsamen Host Sie beschränkt werden kann.

Answer 3

Sie können ein Bitfeld verwenden, um Ihr Sieb zu speichern. Das heißt, es ist in etwa identisch mit einem Booleschen Array, außer dass Sie Ihre Booleans in eine große Ganzzahl packen. Wenn Sie beispielsweise 8-Bit-Ganzzahlen hätten, würden Sie 8 Bit (boolesch) pro Integer speichern, was Ihren Platzbedarf weiter reduzieren würde.

Zusätzlich ermöglicht die Verwendung eines Bitfelds die Verwendung von Bitmasken zur Durchführung des Siebvorgangs. Wenn Ihr Sieb beispielsweise alle Zahlen (nicht nur ungerade) enthält, könnten Sie eine Bitmaske von b01010101 konstruieren, die Sie dann UND für jedes Element in Ihrem Array verwenden können. Für dreier könnten Sie drei ganze Zahlen als Maske verwenden: b00100100 b10010010 b01001001.

Schließlich müssen Sie keine Nummern überprüfen, die niedriger als $n sind, in der Tat müssen Sie nicht für Zahlen unter $n*$n-1 überprüfen.

Answer 4

Sobald Sie wissen, die Nummer ist kein Prime, würde ich die Enter-Schleife verlassen. Ich kenne PHP nicht, aber Sie brauchen eine Aussage wie eine Pause in C oder eine letzte in Perl.

Wenn das nicht verfügbar ist, würde ich ein Flag setzen und es verwenden, um die Inter-Schleife als Bedingung für die Fortsetzung der Interloop zu verlassen. Dies sollte Ihre Ausführung beschleunigen, da Sie $ limit/2 Elemente nicht überprüfen, wenn es kein primäres Element ist.

Answer 5

, wenn Sie Geschwindigkeit wollen, verwenden Sie PHP nicht auf diesen einen: P

nein, im Ernst, ich wirklich wie PHP und es ist eine coole Sprache, aber es ist überhaupt nicht geeignet für solche Algorithmen