+- LabVIEWForum.de (https://www.labviewforum.de)
+-- Forum: LabVIEW (/Forum-LabVIEW)
+--- Forum: LabVIEW Code Beispiele (/Forum-LabVIEW-Code-Beispiele)
+--- Thema: Primzahlen finden (/Thread-Primzahlen-finden)
RE: Primzahlen finden - jg - 09.09.2011 15:25
Bis sqrt(n), das habe ich schon drin gehabt.
Mit Luckis Verbesserungshinweis lande ich bei ca. 210 ms, also Gerd, du bleibst in Führung
Gruß, Jens
RE: Primzahlen finden - Lucki - 09.09.2011 18:38
(09.09.2011 14:35 )GerdW schrieb: 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.Entschuldige meine Vermessenheit, was Du sagst leuchtet ein.
Zitat:1990 habe ich auch angefangen, an Primzahl-Algorithmen zu feilen. In den letzten 2 Jahrzehnten hat sich da einiges getanMeine erste Berührung mit einem Rechner war 1965, es war ein "PDP8" von "Digital Equipment" mit Lochstreifeneingabe und 2k-Magnetkernspeicher. Da habe ich aus Begeisterung und als Hobby Primzahlen berechnet. Mich interessierte dabei, ob es eine Gesetzmäßigkeit gibt, wie die "Primzahldichte" mit höher werdenden Zahlen abnimmt. Weiß aber nicht mehr, was da herausgekommen ist. War vielleicht die Anzahl Primzahlen in jeder Dekade etwa konstant? Keine Ahnung.
RE: Primzahlen finden - jg - 09.09.2011 20:40
Jaja, wie das mit den 640kB Speicher-Zitat
Inzwischen kann ich von der Größenordnung mit Gerd mithalten, ca. 28 ms für 1 Mio auf i7. Aber noch nicht sonderlich optimiert.
Gruß, Jens
RE: Primzahlen finden - GerdW - 09.09.2011 21:44
Hallo Lucki,
Wikipedia (in den 60er/70er Jahren war da ja noch nicht dran zu denken) ist da sehr hilfreich: Anzahl der Primzahlen bis x ~= x/ln(x). Ist eine gute Abschätzung, um Speicher zu reservieren, in dem die Ergebnisse abgelegt werden...
RE: Primzahlen finden - Lucki - 11.09.2011 17:03
(09.09.2011 21:44 )GerdW schrieb: Wikipedia (in den 60er/70er Jahren war da ja noch nicht dran zu denken) ist da sehr hilfreich: Anzahl der Primzahlen bis x ~= x/ln(x). Ist eine gute Abschätzung, um Speicher zu reservieren, in dem die Ergebnisse abgelegt werden...Danke für den Hinweis. Man braucht das Primzahlarray und somit die Abschätzung der Arraygröße aber gar nicht, wenn, wie hier in diesem Thread, nur die Anzahl der Primzahlen ermittelt wird und nicht das Primzahlarray selbst.
Mit Deiner Anregung aus #10 habe ich es mal auf die Schnelle mit einem Sieb versucht. Bei z.B. Max = 1E6 bilde ich ein boolsches Array der Größe 1E6. Die Indizees dieses Arrays, welche Primzahlen sind, haben der Wert true, die anderen false.
Natürlich komme ich nicht auf Deinen Super-Werte, ich muss allerdings auch sagen, daß ich bei meinen PCs immer 50 Euro-CPUs von AMD nehme, oder hier:
CPU Type DualCore AMD Phenom II X2 Black Edition 555, 3200 MHz (16 x 200)
LV2011 [attachment=35799]
RE: Primzahlen finden - jg - 11.09.2011 17:30
@Lucki:
(06.09.2011 15:22 )BNT schrieb: Eingabe: MaximumDoch, doch, es wird auch ein Array mit allen Primzahlen gefordert.
Ausgabe:
- Anzahl der gefundenen Primzahlen
- Array mit den gefundenen Primzahlen
- Zeit in Sekunden, die zur Berechnung nötig waren.
Gruß, Jens
RE: Primzahlen finden - Lucki - 11.09.2011 18:54
(11.09.2011 17:30 )jg schrieb: Doch, doch, es wird auch ein Array mit allen Primzahlen gefordert.Hast Recht, ich dachte nur das SUB-VI in #1 macht das nicht, aber es gibt da doch einen Ausgang für das Primzahl-Array.
Dann verlängert sich meine Zeit auf ca. 20ms:
[attachment=35801]
RE: Primzahlen finden - GerdW - 12.09.2011 08:09
Hallo Lucki,
anbei mal ein "vernünftiges" Bild zum Verdecken von BD-Objekten
P.S.:
Wenn ihr mir jetzt alle auf die Pelle rückt, muss ich mein VI wohl mal auf MultiCore trimmen - bisher läuft es nur auf einem CPU-Kern...
RE: Primzahlen finden - Ome - 12.09.2011 08:47
Hallo,
ich habe mich auch mal versucht um komme auf 150ms bei N=1E6 meine CPU ist ein P8700 @ 2,53 GHz. Ist zwar 'nen bisschen weg von den 20ms aber die CPU ist halt auch nicht so doll.
Gruß Ome
RE: Primzahlen finden - Lucki - 12.09.2011 08:55
(12.09.2011 08:09 )GerdW schrieb: P.S.:Das wird Dir aber nichts nützen, denn die Endwertung erfolgt selbstverständlich nach Yardstick. Das verlangt die Gerechtigkeit, es sollen auch die Habenichtse, die sich ihre CPU von Hartz IV abgespart haben, ihre Chance erhalten.
Wenn ihr mir jetzt alle auf die Pelle rückt, muss ich mein VI wohl mal auf MultiCore trimmen - bisher läuft es nur auf einem CPU-Kern...
Aber trotzden wette ich: Auch bei gleichen CPUs wirst Du nicht zu schlagen sein.