Primzahlen finden

Liebe LabVIEW Fans

Im Rahmen der Betreuung von Schülerpraktikanten lasse ich die Praktikanten zum Einstieg in LabVIEW immer die Primzahlen berechnen.

Aufgabe: Finde alle Primzahlen <= Maximum.

Eingabe: Maximum
Ausgabe:
- Anzahl der gefundenen Primzahlen
- Array mit den gefundenen Primzahlen
- Zeit in Sekunden, die zur Berechnung nötig waren.

Die Aufgabe stelle ich hiermit auch einmal in dieses Forum. Wer findet den schnellten Algorithmus im Sinne Ausführungszeit.
(Eine Array-Konstante mit den Primzahlen zurückgeben, gilt nicht!)

Mein Vergleichsrechner: Dell D830, Intel Core 2 Duo T7700@2.4GHz 3,5 GB RAM, Win XP SP 3, LabVIEW 2011

Es gilt folgende Vorgabe eines Schülerpraktikanten zu schlagen:
Maximum = 1000000
Zeit gemittelt über 100 VI-Aufrufe:
- Mean=833ms
- Std.Dev.=13ms
- Maximum=894ms
- Minimum= 814ms

   

Viel Spaß beim Programmieren. Dem Sieger gebührt Ruhm und Ehre.

Ich werde nach einer angemessesen Zeit die Lösung meines Praktikanten hier einstellen.

Gruß Holger

Anzeige

Hallo BNT,

nur bis 1Mio? Das ist nicht dein Ernst...

Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen

1Mio auf meinem aktuellen Core2Quad benötigen 11.5ms zum Rechnen (hauptsächlich zum Initialisieren der nötigen Datenstrukturen) und mit Ausgabe in ein Array ~50ms:
   

Hallo BNT,

kurzes Update (i5-2410M-2.3GHz):

Code:

Test: Prime_Generator, Bitarray
number    min    mean    max    result
100000    0,000656    0,000698    0,000795    9592
1000000    0,006362    0,006469    0,006619    78498

(min/mean/max in Sekunden, result = Anzahl der Primes)

Hallo GerdW
Das ist ein tolles Ergebnis.

Ich möchte darauf hinweisen, dass es sich bei dem Code, den ich zeigen werde, um denjenigen eines Schülerpraktikanten der Oberstufe handlet. Das Resultat hat er nach drei Stunden erreicht, LabVIEW lernen inklusive!

Ich möchte also allen LabVIEW Fans - auch den Anfängern - Mut machen[/i], zu versuchen, selbst eine Lösung zu finden. Die Laufzeit-Performanz ist bei einem solchen Algorithmus natürlich wesentlich.

Aber auch Lösungen mit wenigen Strukturen können interessant sein, weil sie vermutlich leicht zu verstehen und leicht zu warten sind. Verschiedene Lösungen geben auch Einblick in die Datenflussverarbeitung von LabVIEW. Also welche Programmierstrukturen sind effizient und welche nicht so sehr.

Ich habe die Metrik des VIs angehängt.

Gruß Holger

Bitte nicht wundern. Ich habe das PDF durch ein JPG ersetzt. Ist einfacher zu handhaben.

Gruß Markus

(06.09.2011 15:47 )GerdW schrieb:  Anbei ein PDF mit Messwerten über einen weiten Bereich (x-Achse gibt Maximum in 2^x an, 20 entspricht in etwa deiner 1Mio). Ist schon was älter, der Core2 ist ein T5400 mit 1.6GHz. Und sind nicht meine schnellsten Algorithmen

OK, mit GerdW kann ich nicht mithalten. Gehe ich recht in der Annahme, dass dein Algorithmus kein Trial-and-Error Test ist?!

Ich biete bei 1 Mio bei einem "Trial and Error"-Test mit etwas Knoff-Hoff:
Testsystem i7 unter Win7 /
Bei expliziter Parallelisierung auf 2 Cores ca . 360 ms, ohne Parallisierung ca. 385 ms.

Testsystem Athlon X2 5050e (nicht gerade der Schnellste) unter WinXP /
Bei expliziter Parallelisierung auf 2 Cores ca . 700 ms, ohne Parallisierung ca. 985 ms.

Gruß, Jens

Hallo Jens,

nee, Trial&Error isses nicht, eher das gute alte Sieb!

(09.09.2011 09:23 )GerdW schrieb:  Hallo Jens,

nee, Trial&Error isses nicht, eher das gute alte Sieb!

Aha, dann muss ich nochmal zurück ans Reissbrett.

1990 habe ich mal bei einem Preisausschreiben um das gleiche Problem bei einer PC-Zeitschrift mitgemacht und dafür ein Paket "Power-Basic deutsch" gewonnen. Es steht seitdem unbenutzt auf dem Dachbodenregal und verstaubt.
Ich hatte es glaube ich so gemacht:
Eine Zahl N ist auf Primzahl zu untersuchen. Der Test für alle Zahlen <N wurde schon gemacht, das Array der bisher gefundenen Primzahlen liegt vor. Wenn N keine Primzahl ist und es werden Primfaktoren gefunden, dann muß einer der gefundenen Primfaktoren kleiner als SQRT(N) sein.
Man muß also die Zahl N durch die bisher gefunden Primzahlen im Bereich 2..SQRT(N) zu teilen versuchen. Wenn der Rest niemals Null ist, ist N eine neue Primzahl. Sowie ein Rest Null ist, wird die Suche abgebrochen werden und die nächste ungerade Zahl getestet.
So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht.
Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!

Hallo Lucki,

Zitat:So ungefähr, und vielleicht mit noch eine paar zusätzlichen Tricks, damit es so schnell wir möglich geht. Mir diesem Hinweis sollte es doch möglich sein, es mit Gerd aufzunehmen!

Nichts für ungut, aber das bezweifel ich! Die Q&R-Funktion (oder auch die Divide) sind dafür einfach zu langsam. Mit einem Sieb ist man da immer schneller - man muss nur genügend Speicher reservieren können. Wobei das heute auch kein großes Problem mehr darstellt: um alle Zahlen bis 2^32 zu sieben, benötigt man "nur" ~137MB für eine Routine "mittlerer" Geschwindigkeit. (Wenn's wirklich schnell sein soll, wären 2GB am Stück und ein 64bit-OS/LV nötig.)

1990 habe ich auch angefangen, an Primzahl-Algorithmen zu feilen. In den letzten 2 Jahrzehnten hat sich da einiges getan