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(n)
{
z:=prims[A_Index]
if not mod(n,z)
{
prim=0
break
}
}
if prim
prims.insert(n)
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