Sieb des Eratosthenes

[ralfkannenberg]

Über den Daumen gepeilt entspricht das dem Alter des Universums.

Da muss man also schon wirklich viel Geduld mitbringen .

Hallo Bernhard,

es war sogar 150'000x länger als diese 10^17 Sekunden, genau wie Du schreibst das Alter des Universums. Ich habe daraufhin meine Versuche mit dem Backtracking-Algorithmus eingestellt und meine Frage, warum man das Problem Mitte der 1960-iger Jahre nicht mit Computer-Hilfe gelöst hat, war damit auch schon beantwortet.

Das war damals schon das zweite Mal, dass ich ein Programm geschrieben hatte, dessen Laufdauer länger als das Alter des Universums war; das erste Mal war beim Bestimmen der Untergruppen im Rahmen meiner damaligen Semesterarbeit mit CAYLEY passiert, wo ich die Aufgabe mit purer Rechenleistung erschlagen wollte (natürlich auch sehr zur "Freude" besagten Oberassistenten) und dann eben schliesslich doch die Mathematik bemühen musste. - Wenn ich mich recht entsinne hatte ich es damals mit 28! zu tun.


Freundliche Grüsse, Ralf

 

[Kibo]

Hallo zusammen,

vielleicht erinnert sich noch jemand an diesem Thread, wo ich etwas ähnliches gepostet habe. Falls Bedarf besteht, ich habe den Sourcecode noch.

 

[Bernhard]

vielleicht erinnert sich noch jemand an diesem Thread, wo ich etwas ähnliches gepostet habe.

Hallo Kibo,

ist schon ne Weile her, aber ich habe das Thema gerne nochmal gelesen und bin über einen deinen YT-Link (?) weiter auf den folgenden unterhaltsamen Link gestossen: Glitch Primes and Cyclops Numbers - Numberphile (07.12.2015). Interessante Beweisidee (habe es noch nicht komlett nachvolllzogen) am Ende, dass 101 die einzige prime Zyklopen-Binärzahl ist.

Falls Bedarf besteht, ich habe den Sourcecode noch.

Ja. Ich würde gerne einen Blick auf den Algorithmus werfen. Hast ja vermutlich auch "gesiebt" und da würde ich gerne mal sehen, wie du es umgesetzt hast.

Kannst wegen mir gerne auch den "Sieb-Code" hier posten. Dann spart man sich den Download.

 

[Kibo]

Gerne hier der doch sehr kurze Kern:


pixelmenge:=10000
gestrichen:=Object()
prims:=Object()
prims.insert(2)
n=3

SetTimer render, 200

Loop 100000
{
prim=1
z=1
while z<sqrt
{
z:=prims[A_Index]
if not mod(n,z)
{
prim=0
break
}
}
if prim
prims.insert
n+=2

}

 

[Bernhard]

OK. Interessant.

Mit n+=2 werden die geraden Zahlen ausgeschlossen.

Ist das Visual-Basic?

 

[ralfkannenberg]

Mit n+=2 werden die geraden Zahlen ausgeschlossen.

Hallo Bernhard,

Primzahlen grösser gleich 3 sind stets ungerade.

Man kann die Bestimmung der nächsten Primzahl übrigens weiter optimieren, da Zahlen modulo 5 bis auf die 5 selber keine Primzahlen sind und auch ungerade Vielfache von 3 keine Primzahlen sind:

2 prim (gesetzt)
3 prim (Startpunkt)
5 prim (Startpunkt+2)
7 prim (+2)
9 nicht-prim (3+6)
11 prim (+2)
13 prim (+2)
15 nicht-prim (3+2*6 sowie modulo 5)
17 prim (+2)
19 prim (+2)
21 nicht prim (3+3*6)
23 prim (+2)
25 nicht-prim (modulo 5)
27 nicht-prim (3+4*6)
29 prim
31 prim
33 nicht-prim (3+5*6)
35 nicht-prim (modulo 5)

u.s.w.

d.h. wenn man hier etwas clever den nächsten Primzahlkandidaten bestimmt, dann ist 49 (7*7) die erste Nicht-Primzahl, die nicht durch die Kriterien "nicht gerade", "nicht 3+n*6" und "nicht modulo 5" bereits ausgeschlossen wird, die nächste ist dann erst 77 (7*11) und bis 100 gibt es nur noch eine weitere, nämlich 91 (7*13).

Man hat dann also bis 100 nur drei "Fehlalarme".


Und eine Addition ist auf jeden Fall schneller als mod(3) und mod(5) zu bestimmen. Allerdings muss man hierfür auch die 5 fix in den Primzahlspeicher setzen, kann also erst bei 5 anfangen, hochzuaddieren.


Freundliche Grüsse, Ralf

 

[Bernhard]

Und eine Addition ist auf jeden Fall schneller als mod(3) und mod(5) zu bestimmen.

Hallo Ralf,

wie bereits im ersten Beitrag erwähnt, sehe ich eine Begrenzung nicht bei der Geschwindigkeit, sondern eher beim Speicherbedarf, wenn man möglichst viele Primzahlen berechnen will.

Deshalb erscheint mir eine Vorauswahl an möglichen Zahlen eher als sinnvoll. Mit der vorgeschlagenen Möglichkeit im ersten Beitrag kann man die höchste berechenbare Primzahl allerdings von <1e9 schätzungsweise auch nur auf <1e11 oder <1e12 heben, womit man dann die Kapazität des Rechners insgesamt wohl auch schon optimal nutzt.

 

[ralfkannenberg]

sehe ich eine Begrenzung nicht bei der Geschwindigkeit, sondern eher beim Speicherbedarf, wenn man möglichst viele Primzahlen berechnen will.

Deshalb erscheint mir eine Vorauswahl an möglichen Zahlen eher als sinnvoll. Mit der vorgeschlagenen Möglichkeit im ersten Beitrag kann man die höchste berechenbare Primzahl allerdings von <1e9 schätzungsweise auch nur auf <1e11 oder <1e12 heben, womit man dann die Kapazität des Rechners insgesamt wohl auch schon optimal nutzt.

Hallo Bernhard,

das ist wohl alles richtig, wobei ich das sehr schlecht beurteilen kann, weil ich beruflich weder mit rechenintensiven noch mit speicherintensiven Aufgabenstellungen zu tun habe; was ich allerdings nicht ganz verstehe ist, warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.

Und um Missverständnissen vorzubeugen: als Mathematiker rede ich von exakten Primzahlprüfungen, d.h. nicht von solchen, die eine hohe Wahrscheinlichkeit aufweisen und für Verschlüsselungen und Hacker völlig genügend sind.


Freundliche Grüsse, Ralf

 

[Bernhard]

was ich allerdings nicht ganz verstehe ist, warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen

Hallo Ralf,

mich interessieren die exakten Werte der Primzahlfunktion und da ist es naheliegend die leicht zugänglichen Werte über das Sieb dE zu berechnen. Zudem ist das eine nette und vergleichsweise sehr leicht zu lösende Programmieraufgabe. Man hat also schnell ein Erfolgserlebnis.

statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.

Ich kenne Online-Listen nur bis 1e6. Das Sieb liefert die exakten Zahlen mit sehr geringem Aufwand bis 1e9.

 

[astrofreund]

... warum verschiedene Leute eine riesige Anzahl Primzahlen berechnen wollen statt diese einfach in einer riesigen Bibliothek, auf die jeder zugreifen kann, abzulegen.

Hallo Ralf,

ich vermute, dass es ähnliche Gründe sind, weshalb immer mehr Nachkommastellen von Pi berechnet werden.

Gruß, Astrofreund

 

[Kibo]

...

Ist das Visual-Basic?

Das ist in Autohotkey geschrieben, eine sehr bequeme Interpretersprache die z.B. auch opengl kann

 

[Bernhard]

Das ist in Autohotkey geschrieben

OK. Der Code sieht tatsächlich recht übersichtlich aus.

 

[Kibo]

Ich hab dir den gesamten Sourcecode auf mein Onedrive hochgeladen. Benötigt werden primpixel 4.ahk, GLini.ahk und gl.ahk. Die kompilierten exes von 2015 liegen da auch noch. Das waren noch Zeiten...

https://1drv.ms/u/s!AmLG71NEfTlYhwYybd-6glvv4K8E?e=UclLkG

 

[Bernhard]

Ich hab dir den gesamten Sourcecode auf mein Onedrive hochgeladen. Benötigt werden primpixel 4.ahk, GLini.ahk und gl.ahk. Die kompilierten exes von 2015 liegen da auch noch.

Prima. Tut. Danke

Das waren noch Zeiten...

Ist ne Weile her, ja . "Damals" gab es noch kein SpaceX-Starship zum ansehen

 

[Bernhard]

mich interessieren die exakten Werte der Primzahlfunktion

Nach einiger Suche im www möchte dazu diese Seite https://en.wikipedia.org/wiki/Meissel–Lehmer_algorithm und insbesondere die zugehörige Referenz 1 empfehlen.

Das zugehörige pdf ist auch auf der deutschen Seite zu https://de.wikipedia.org/wiki/Ernst_Meissel verlinkt.

Nebenbei: Lesenswert finde ich auch: https://de.wikipedia.org/wiki/Waringsches_Problem

 

[Bernhard]

Hier: https://codegolf.stackexchange.com/questions/74269/calculate-the-number-of-primes-up-to-n findet man Implementierungen des Siebs in weiteren Programmiersprachen, innerhalb eines Wettbewerbs zum schnellsten Berechnen einiger Werte der Primzahlfunktion bis 2e9. Der erste Beitrag verwendet dabei die Formeln von Referenz 2 des vorher angegebenen Links zum Meissel-Lehmer-Algorithmus.

Auch interessant und unterhaltsam: Mathe RÄTSEL Primzahlen – Knifflige Rätsel

 

[Bernhard]

Da die Programmierung des Siebs nicht gerade viel Diskussionsstoff liefert, erweitere ich das Thema auf die exakte Berechnung der Primzahlfunktion. Zwei Referenzen sind dafür bereits über die Seite: https://en.wikipedia.org/wiki/Meissel–Lehmer_algorithm frei verfügbar.

Meine Erfahrungen mit der Programmierung der dort vorgestellten Verfahren möchte ich hiermit gerne zur Diskussion und zur Verwendung stellen:

a) Das "Sieb" liefert mit einem handelsüblichen Büro-PC relativ leicht und in überschaubarer Zeit alle Primzahlen < 1e9. Begrenzender Faktor ist dort eher der Speicher, da man mit einer wenig aufwändigen Programmierung ca. 0.5e9 Bits für das Sieb vorhalten muss. Daraus ergibt sich überschlägig eine Speicherbelegung von 1e9 Byte, was ungefähr 1 GB RAM entspricht.

b) Mit dem Meissel-Lehmer-Algorithmus kann man mit diesem Sieb dann zB den maximalen Wert von pi(1e13) berechnen, wobei dann die Rechenzeit schon mehrere Minuten betragen kann. Bei meiner Implementierung liege ich aktuell für diesen Wert bei ca. 20 Minuten Rechenzeit. Der korrekte Wert für pi(1e13) kann mit den Werten dieser Seite https://de.wikipedia.org/wiki/Primzahlsatz#Zahlenbeispiele kontrolliert werden.

Für größere Werte für pi(x) wird bei Verwendung des normalen Meissel-Lehmer-Algorithmus von 1958 vor allem die Rechenzeit problematisch. Durch eine rekursive Anwendung des Gesamtalgorithmus für pi(x) scheint der Wert für pi(1e14) auch noch berechenbar zu sein, allerdings habe ich die Programmausführung nach einer Stunde Rechenzeit dann abgebrochen.

Problematisch bezüglich der Rechenzeit ist ab pi(1e13) nur die (rekursive) Berechnung der Funktion phi(x,a). Für diese Berechnung findet man in der Veröffentlichung des erweiterten Meissel-Lehmer-Algorithmus eine neue Abbruchbedingungen, welche die Laufzeit reduzieren sollte.

 

[Bernhard]

Per Suchmaschine findet man schnell interessante Treffer zum erweiterten Meissel-Lehmer-Algorithmus, wie zB eine Implementierung in C: https://github.com/jfkingiii/meissel-lehmer .

Ich habe den zentralen Quelltext von hier: https://github.com/jfkingiii/meissel-lehmer/blob/master/prototype/ML_test.c mal für MS-Visual Studio C++ angepasst und damit dann pi(1e13) berechnen lassen.

Das korrekte Ergebnis war dann auch nach ca. 1-2 Minuten Rechenzeit zu sehen, was eine beeindruckende Verkürzung der Rechenzeit im Vergleich zum normalen Meissel-Lehmer-Verfahren zeigt.

Bei der Berechnung von pi(1e14) ergeben sich dann neue Probleme bei der Speicherbelegung.

 

[Bernhard]

Vorerst abschließend noch ein Motivationsvideo: Why do prime numbers make these spirals? | Dirichlet’s theorem, pi approximations, and more

 

[Major T.O.M.]

Hallo Bernhard,

Das was du im Startbeitrag geschrieben hast, hatte ich mir auch schonmal überlegt. Ich hab dann aber festgestellt, dass es nach der 3 dann nicht mehr viel bringt. Im Prinzip reduziert man ja die Größe mit jeder Primzahl p auf (p-1)/p. Also 1/2, 2/3, 4/5, 6/7, 10/11,... und sobald das Primzalprodukt größer n ist, ist dann ja auch schon Schluss. Das erreicht man ja auch relativ schnell.

Ich hatte das mal so implementiert, dass ich immer Kopien erstellt habe und vielfache des Primzahlprodukts draufaddiert habe. Also Angefangen mit

[1, 5]

Fünf "Kopien" (bzw. ein Orginal und 4 "Kopien"):

[1, 5, 7, 11, 13, 17, 19, 23, 25, 29]

5 und 25 werden rausgestrichen, da sie durch 5 teilbar sind. Dann 7 "Kopien" (bzw. ein Orginal und 6 "Kopien").

[1, 7, 11, 13, 17, 19, 23, 29, 31, 37,...,199, 203, 209]

Alle durch 7 Teilbaren rausstreichen usw.

Dabei muss vorher immer noch überprüft werden, ob das Primzalprodukt n übersteigt. Wenn das der Fall ist, machst du entsprechend weniger Kopien und die letzte Kopie sollte dann auch schon früher abgeschnitten werden.