INFO: Dieses Forum nutzt Cookies...
Cookies sind für den Betrieb des Forums unverzichtbar. Mit der Nutzung des Forums erklärst Du dich damit einverstanden, dass wir Cookies verwenden.

Es wird in jedem Fall ein Cookie gesetzt um diesen Hinweis nicht mehr zu erhalten. Desweiteren setzen wir Google Adsense und Google Analytics ein.


Antwort schreiben 

Primzahlen finden



Wenn dein Problem oder deine Frage geklärt worden ist, markiere den Beitrag als "Lösung",
indem du auf den "Lösung" Button rechts unter dem entsprechenden Beitrag klickst. Vielen Dank!

09.09.2011, 15:25
Beitrag #11

jg Offline
CLA & CLED
LVF-Team

Beiträge: 15.806
Registriert seit: Jun 2005

20xx / 8.x
1999
EN

Franken...
Deutschland
RE: Primzahlen finden
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 Smile

Gruß, Jens

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung. (Leonardo da Vinci)

!! BITTE !! stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort!

Einführende Links zu LabVIEW, s. GerdWs Signatur.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 18:38 (Dieser Beitrag wurde zuletzt bearbeitet: 10.09.2011 08:18 von Lucki.)
Beitrag #12

Lucki Offline
Tech.Exp.2.Klasse
LVF-Team

Beiträge: 7.697
Registriert seit: Mar 2006

LV 2016-18 prof.
1995
DE

01108
Deutschland
RE: Primzahlen finden
(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 getan Smile
Meine 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.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 20:40
Beitrag #13

jg Offline
CLA & CLED
LVF-Team

Beiträge: 15.806
Registriert seit: Jun 2005

20xx / 8.x
1999
EN

Franken...
Deutschland
RE: Primzahlen finden
Jaja, wie das mit den 640kB Speicher-Zitat Big Grin

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

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung. (Leonardo da Vinci)

!! BITTE !! stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort!

Einführende Links zu LabVIEW, s. GerdWs Signatur.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
09.09.2011, 21:44
Beitrag #14

GerdW Offline
______________
LVF-Team

Beiträge: 17.067
Registriert seit: May 2009

LV2020
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
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...

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
11.09.2011, 17:03
Beitrag #15

Lucki Offline
Tech.Exp.2.Klasse
LVF-Team

Beiträge: 7.697
Registriert seit: Mar 2006

LV 2016-18 prof.
1995
DE

01108
Deutschland
RE: Primzahlen finden
(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    
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
11.09.2011, 17:30
Beitrag #16

jg Offline
CLA & CLED
LVF-Team

Beiträge: 15.806
Registriert seit: Jun 2005

20xx / 8.x
1999
EN

Franken...
Deutschland
RE: Primzahlen finden
@Lucki:
(06.09.2011 15:22 )BNT schrieb:  Eingabe: Maximum
Ausgabe:
- Anzahl der gefundenen Primzahlen
- Array mit den gefundenen Primzahlen
- Zeit in Sekunden, die zur Berechnung nötig waren.
Doch, doch, es wird auch ein Array mit allen Primzahlen gefordert.

Gruß, Jens

Wer die erhabene Weisheit der Mathematik tadelt, nährt sich von Verwirrung. (Leonardo da Vinci)

!! BITTE !! stellt mir keine Fragen über PM, dafür ist das Forum da - andere haben vielleicht auch Interesse an der Antwort!

Einführende Links zu LabVIEW, s. GerdWs Signatur.
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
Anzeige
11.09.2011, 18:54
Beitrag #17

Lucki Offline
Tech.Exp.2.Klasse
LVF-Team

Beiträge: 7.697
Registriert seit: Mar 2006

LV 2016-18 prof.
1995
DE

01108
Deutschland
RE: Primzahlen finden
(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:

   
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
12.09.2011, 08:09 (Dieser Beitrag wurde zuletzt bearbeitet: 12.09.2011 08:13 von GerdW.)
Beitrag #18

GerdW Offline
______________
LVF-Team

Beiträge: 17.067
Registriert seit: May 2009

LV2020
1995
DE_EN

10×××
Deutschland
RE: Primzahlen finden
Hallo Lucki,

anbei mal ein "vernünftiges" Bild zum Verdecken von BD-Objekten Smile

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...


Angehängte Datei(en) Thumbnail(s)
   

Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
12.09.2011, 08:47
Beitrag #19

Ome Offline
LVF-Gelegenheitsschreiber
**


Beiträge: 109
Registriert seit: Nov 2009

2011
2009
DE

12XXX
Deutschland
RE: Primzahlen finden
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
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
12.09.2011, 08:55
Beitrag #20

Lucki Offline
Tech.Exp.2.Klasse
LVF-Team

Beiträge: 7.697
Registriert seit: Mar 2006

LV 2016-18 prof.
1995
DE

01108
Deutschland
RE: Primzahlen finden
(12.09.2011 08:09 )GerdW schrieb:  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...
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.
Aber trotzden wette ich: Auch bei gleichen CPUs wirst Du nicht zu schlagen sein. Big Grin
Alle Beiträge dieses Benutzers finden
Diese Nachricht in einer Antwort zitieren to top
Antwort schreiben 


Möglicherweise verwandte Themen...
Themen Verfasser Antworten Views Letzter Beitrag
  Farbe finden und verfolgen snuz 3 5.549 25.05.2011 07:27
Letzter Beitrag: unicorn

Gehe zu: