Primzahlen ermitteln?

**Nikolas**

Du musst für fast jede untersuchte Zahl eine Muliplikation machen, und ich nur eine Wurzel ziehen. Bei größeren Zahlen könnte sich das bemerkbar machen.

**3_of_8**

Ja, bei größeren Zahlen mit Sicherheit.

Übrigens: Ich habe hier gerade ein Sieb des Erathostenes mithilfe eines Bitvektors realisiert und innerhalb von 74 Sekunden alle Zahlen von 0 bis 2^28 überprüft. Sollte Interesse bestehen, kann ich den Code mal posten.

**ThE_-_BliZZarD**

*Interesse anmeld*
Poste mal bitte den Code

**3_of_8**

Bittesehr, sogar ein kleines bisschen schneller als die verbesserte Version in der CL, die ich erst nachträglich gefunden habe. Im übrigen, die reine Berechnung von 2^28 Werten geht in 20 Sekunden, die restlichen 54 gingen für die Ausgabe in die Dateien (56 MB) drauf.

**alzaimar**

Es geht auch in ca. 1.5 Sekunden,

hier

**3_of_8**

Aber nur mit einer Art hartkodierten Primzahltabelle bis ~2^15, wenn ich das richtig sehe.

**alzaimar**

Auch Ohne wär es schneller, denn es verwendet eine Optimierung von Atkin. Das Erzeugen aller 16-bit Primzahlen dauert doch auch nur ein paar 100ms.

Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Re: Primzahlen ermitteln?

Forumregeln

Nikolas Registriert seit: 28. Jul 2003 1.528 Beiträge Delphi 2005 Personal	#21 Re: Primzahlen ermitteln? 11. Mai 2007, 21:09 Du musst für fast jede untersuchte Zahl eine Muliplikation machen, und ich nur eine Wurzel ziehen. Bei größeren Zahlen könnte sich das bemerkbar machen. Erwarte das Beste und bereite dich auf das Schlimmste vor.
	Zitat

ThE_-_BliZZarD Registriert seit: 15. Sep 2006 Ort: Wiesbaden/Hessen 89 Beiträge Delphi 2010 Professional	#23 Re: Primzahlen ermitteln? 11. Mai 2007, 23:53 Interesse anmeld Poste mal bitte den Code MSVC2008 (C/C++ with QT), Delphi RAD 2010, Flash CS5 (FDT/Adobe), Java EE (Eclipse), PHP5 Antwortsprachen: Deutsch, Englisch, Französisch, Japanisch
	Zitat

alzaimar (Moderator) Registriert seit: 6. Mai 2005 Ort: Berlin 4.956 Beiträge Delphi 2007 Enterprise	#25 Re: Primzahlen ermitteln? 12. Mai 2007, 09:05 Es geht auch in ca. 1.5 Sekunden, hier "Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!" (Monty Python "Joke Warefare")
	Zitat

3_of_8 Registriert seit: 22. Mär 2005 Ort: Dingolfing 4.129 Beiträge Turbo Delphi für Win32	#26 Re: Primzahlen ermitteln? 12. Mai 2007, 10:19 Aber nur mit einer Art hartkodierten Primzahltabelle bis ~2^15, wenn ich das richtig sehe. Manuel Eberl „The trouble with having an open mind, of course, is that people will insist on coming along and trying to put things in it.“ - Terry Pratchett
	Zitat

alzaimar (Moderator) Registriert seit: 6. Mai 2005 Ort: Berlin 4.956 Beiträge Delphi 2007 Enterprise	#27 Re: Primzahlen ermitteln? 12. Mai 2007, 11:19 Auch Ohne wär es schneller, denn es verwendet eine Optimierung von Atkin. Das Erzeugen aller 16-bit Primzahlen dauert doch auch nur ein paar 100ms. "Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!" (Monty Python "Joke Warefare")
	Zitat