Diskussion:Sieb des Eratosthenes

Zu Beginn alles Primzahlen

Ich finde es verwirrend, alle zu Beginn gewählten Zahlen Primzahlen zu nennen. Das würde bedeuten, dass sich die Zahlen, die tatsächlich Primzahlen sind, im Verlauf des Verfahrens ändern. (nicht signierter Beitrag von M3~dewiki (Diskussion | Beiträge) 01:24, 9. Aug. 2004‎ (CEST))

Primzahlentabellen

Die Bemerkung, dass Verfahren sei gut geeignet Primzahlentabellen zu erstellen wurde ergänzt. Ich sehe dies aber eher anders herum. Das Verfahren zeigt, dass Primzahlentabellen im Grunde völlig sinnlos sind. Das einfache, schon in der Antike bekannte Verfahren, erlaubt es alle Primzahlen bis zu einer Schranke in kürzester Zeit zu berechnen. Tatsächlich ist die erforderliche Zeit zur Berechnung aller Primzahlen etwa kleiner einer Million auf einem Rechner mit dem Sieb des Eratosthenes allenfalls eine Frage von Sekunden. Die Rechenzeit ist praktisch zu vernachlässigen. Lediglich der erforderlich Speichplatz ist dabei von Bedeutung. Eine Primzahlentabelle kann folglich bei Bedarf jederzeit neu berechnet werden. Benutzer:Fsswsb 29.05.06 (falsch signierter Beitrag von Fsswsb (Diskussion | Beiträge) 21:57, 29. Mai 2006 (CEST))

Auch wenn eine Primzahlentabelle bei Bedarf jederzeit neu berechnet werden kann, erzeugt man dabei eine Primzahltabelle. Diese Aussage erzeugt also keinen Widerspruch. Du gehst hier fälschlicherweise davon aus, dass die Erzeugung einer Primzahltabelle immer mit einer permanenten Speicherung verbunden ist. --Squizzz 23:11, 29. Mai 2006 (CEST)

Nur als kleiner Hinweis: Eratosthenes hatte noch keinen Computer und in einer gut sortierten Unibibliothek findet man heute noch dicke Bücher, in denen einfach nur die ersten 100.000 Primzahlen durchnummeriert zu finden sind. Sinnlos? Ja, heute schon! --Suricata 09:41, 30. Mai 2006 (CEST)

Anmerkung überflüssig

Im vorangehenden Text steht es bereits: Es genügt mit dem Quadrat der Primzahl zu beginnen, weil alle kleineren Zahlen bereits markiert sind.

Mehr ist dazu eigentlich nicht zu sagen. Die kleineren Vielfachen haben zwangsläufig einen kleineren Primteiler und sind daher bereits gestrichen. Wer will kann sie aber auch mehrfach streichen. Benutzer:Fsswsb 29.05.06 (falsch signierter Beitrag von Fsswsb (Diskussion | Beiträge) 22:07, 29. Mai 2006 (CEST))

Sieb-Animation

Ich finde es schön, wenn verschiedene Benutzer eine Animation erstellen wollen, mit einem weniger pixeligen Zeichensatz und nicht so grellen Farben. Eine Animation die etwas langsamer abläuft, und bei denen das Ergebnis am Ende etwas längere stehen bleibt.

Nicht das man mich mißversteht: Wenn ich die Animation nicht erstellt hätte, würde ich auch bei der Abstimmung für exzellente Bilder mit contra stimmen. Aber es soll niemand davon ausgehen, daß ich mich jetzt hinsetzte, und die Animation neu machen. Wem das mit der Verbesserung der Animation ernst ist, der muß sich selber ransetzen.

Die einzige Sache, die ich mir selbst vorwerfen kann ist, das ich nur bis hundert gegangen bin, und nicht bis hundertzwanzig. Warum bis hundertzwanzig? 11² ist 121. Die untere Grenze wäre 48 (7²-1), aber das wäre ein bisschen wenig.

Ich harre also der Dinge, die da kommen. --Arbol01 23:02, 18. Aug 2004 (CEST)

Wohlan! Ich hoffe, die neue Animation gefällt. Schön bunt, nicht? :-) Die GIF ist übrigens automatisch erzeugt, so daß ich prinzipiell auf Änderungswünsche ohne große Mühen eingehen kann.

Den eichensalat in Haskell und Perl habe ich herausgenommen. IMHO hat das keinen Informationswert. --Sebastian Koppehel 02:52, 12. Okt 2004 (CEST)

Änderungswünsche ??? Ja, kann ich mit dienen: Ich würde bis 120 gehen. Da ist die 11 gerade eben noch nicht drinnen.

Eichensalat? Das sind Quellcodes, in den entsprechenden Programmiersprachen (Haskell und Perl) geschrieben. Aber ich gebe zu, das sie kryptisch und unverständlich sind. In Primzahltest ist unter dem Punkt Sieb des Erathostenes ein relativ verständlicher Code abgebildet, und vielleicht füge ich noch einen Code in REXX ein. --Arbol01 03:08, 12. Okt 2004 (CEST)

Es sollte natürlich "Zeichensalat" heißen. Dankeschön, daß das Programme sein sollten, war mir schon klar. Ich halte sie trotzdem für nicht sehr informativ, und wer Perl oder Haskell nicht kennt, der versteht erst recht nichts.

Wie du schreibst, kann man bis 120 gehen, man kann sogar noch viel weiter gehen, aber will man das wirklich? Die Sache wird dadurch nur noch länger. Ich hielt 100 eigentlich schon für eine ganz gute Grenze. Hier ist die alternative Version mit Obergrenze 120:

Eine weitere Änderung gegenüber der ersten Version: Die Vielfache der höheren Primzahlen überschreiben Vielfache der niedrigeren. Auf diese Weise kann man das 1x3, das 1x5 und das 1x7 erkennen. Die Graphik ist jetzt satte 3,4 MB groß. --Sebastian Koppehel 12:35, 12. Okt 2004 (CEST)

Du hast mich etwas mißverstanden. Es geht mir nicht darum, die Sieb-Animation bis ins unendliche auszudehnen. 120 wäre sozusagen der Idealfall, wenn man bis 7 Aussiebt, weil man bei der 11 eben bei 121 anfangen muß herauszusieben. Wenn man bis zur 5 heraussiebt, dann wäre 48 die ideale Grenze, da 7*7 = 49 ist. --Arbol01 12:45, 12. Okt 2004 (CEST)

Ich fürchte allerdings, die Animation wird zu lang und die Datei zu groß. --Sebastian Koppehel 14:53, 12. Okt 2004 (CEST)

Nachtrag: Nichts gegen das Überschreiben, aber Du solltest bei den Quadraten beginnen, also nicht mehr die 6, 10, 15, 20, 14, 21, 28, 35 und 42 überschreiben, weil das ein guter Algorhitmus nicht machen würde. --Arbol01 12:53, 12. Okt 2004 (CEST)

[x] done --Sebastian Koppehel 14:53, 12. Okt 2004 (CEST)

So, nun ist die Animation nur noch 190 kB groß. Gleiche Bildelemente, die sich nicht verändern, wurden aus der Animation entfernt (mit dem ULEAD-Gif Animator). --Arbol01 15:43, 12. Okt 2004 (CEST)

Bildlink geändert. Die Version mit "(120)" ist jetzt überflüssig. Und ich konnte gifsicle jetzt auch dazu überreden, das zusammengesetzte Bild zu optimieren. --Sebastian Koppehel 01:40, 13. Okt 2004 (CEST)

Ich möchte mal dezent darauf hinweisen, dass die Animation zu langatmig abläuft. Während der ersten 60 Sekunden passiert nichts weiter, als dass alle geraden Zahlen rot angemalt werden. Das ist vielleicht würdig für die Erklärung der geraden Zahlen bis 120, aber nicht für das hier zu behandelnde Sieb. Ob der Rest der Animation aussagekräftig ist, kann ich nicht sagen - ich bin nach einer halben Minute roter Kästchen eingeschlafen.. Vorschlag: Limitierung auf 60 oder noch weniger. Es geht ja nur ums Prinzip und nicht darum, wer die meisten Primzahlen in einem Kasten unterbringt.

Es wäre davon abgesehen sinnvoll, wenn der aktuelle Arbeitsschritt beschrieben werden würde. Momentan steht da nur "2", beschreibend wäre "Vielfache von 2 aussortieren", danach wohl "Vielfache von 3 aussortieren", usw.

Und weil ich rechtzeitig wieder aufgewacht bin (wie lange läuft das, fünf Minuten?): Das Endergebnis verschwindet, bevor man einen Überblick gewonnen hat. (nicht signierter Beitrag von 84.245.183.207 (Diskussion) 13:39, 17. Sep. 2005 (CEST))

Hallo, ich wollte zu der Animation nur sagen, dass wenn die Felder grün werden (also 3er), zwar 3 und 9 usw. grün werden, aber die 6 wird irgendwie ausgelassen ;) (nicht signierter Beitrag von 84.139.109.225 (Diskussion) 01:11, 26. Jan. 2006 (CET))

Dass die 3 in der Animation vergisst, die 6 zu markieren gehört so und steht auch im Text. Das langsame Markieren der geraden Zahlen erlaubt es, selbige zu lesen. :-)

Die sechs wird ausgelassen, weil erst beim Quadrat angefangen wird auszusoriteren.

Bei der Geschwindigkeit gebe ich dir aber recht. Viel zu langsam. Sollte auch so ablaufen, wie die zweite Animation. Denn spätestens bei der 10 hat man verstanden, dass alle durch zwei Teilbaren Zahlen aussortiert werden. Zudem finde ich, dass die Primzahlen grün markiert werden sollten, und die "Dreier" lila. Da drunter dann noch eine Legende, damit auch der letzte Versteh: Ah, die grünen Zahlen sind die Primzahlen. Ich habe das erst beim zweiten Durchlauf gecheckt. --84.158.125.26 11:29, 29. Jan. 2013 (CET)

Bild beschleunigen

Die Franzosen haben das Bild etwas beschleunigt:

• http://upload.wikimedia.org/wikipedia/fr/d/d6/Animation_Sieb_des_Eratosthenes_mod.gif schnell
• http://upload.wikimedia.org/wikipedia/commons/6/63/Animation_Sieb_des_Eratosthenes.gif langsam

Mir gefällt das schnellere besser. Wenn diese mehrheitlich so ist, würde ich den Autor bitten, das langsame Bild auf den Commons durch das schnellere zu ersetzen. Ich bitte daher um Eure Meinung. (Da das Bild exzellent ist wären ein paar bestätigende Stimmen hierzu sinnvoll) --Suricata 08:17, 12. Apr 2006 (CEST)

Da keine Einwände kamen habe ich das langsame Bild durch das schnelle ersetzt. Die Exzellenz sollte dadurch nicht gefährdet sein. --Suricata 09:17, 23. Mai 2006 (CEST)

...unsinnig langatmige Erklärung?

Was Benutzer:Fsswsb rausgeworfen hat, war wirklich eine langwierige Erklärung mit Tabellen. Ich kopier sie mal hierher:

„Das Sieb des Eratosthenes kann wie folgt beschrieben werden:

Es sollen die Primzahlen zwischen 2 (der ersten Primzahl) und einem Maximum m (im Beispiel: m=62) ermittelt werden.

1. Zunächst wird das Zahlenfeld initialisiert. Alle Zahlen von 2 bis m sind unmarkiert:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ...

2. Die Variable n ist die jeweils zu bearbeitende Zahl. Sie wird auf 2 initialisiert.

n = 2

3. Alle Vielfachen von n im Zahlenfeld werden gestrichen; dabei kann mit dem Streichen bei n² begonnen werden, da die kleineren Vielfachen von n beim kleineren Faktor bereits gestrichen wurden:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ...

4. n wird auf die nächste unmarkierte Zahl gesetzt.

Zunächst ist also n = 3

5. Schritte 3 und 4 werden solange wiederholt, bis n² größer als m ist.
Also werden als nächstes die (noch vorhandenen) Vielfachen von 3 gestrichen:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ...

... danach die verbliebenen Vielfachen von 5:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ... 

... danach restlichen die Vielfachen von 7:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ... 

... und so weiter.

Die übrig gebliebenen, fett gedruckten Zahlen sind die gesuchten Primzahlen.

Der Prozess wird abgebrochen, wenn n² > m ist; die letzte zu bearbeitende Zahl ist also die n = 7, weil 8² = 64 > 62.

Das Ergebnis ist dann:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 
31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
61 62 ...

“ - Ende des Zitats

Ich bin mir auch nicht sicher, ob diese Erklärung neben der animierten Demonstration wirklich nötig ist. Was jetzt allerdings als unter „Funktionsweise“ steht, ist unverstehbar bis falsch und muss dringend überarbeitet werden.

Wenn die Animation als einzige Beschreibung im Artikel bleiben soll, hätte ich dazu noch zwei Vorschläge:

1. Die „erkannten“ Primzahlen sollen von Anfang an lila erscheinen.
2. Auf den „Beschleunigungstrick“, mit dem Streichen erst bei i² zu beginnen, sollten wir verzichten. Er ist für das Verständnis des Verfahrens unwesentlich und bringt nur Verwirrung (siehe z.B. den Anfang dieser Diskussion).

Dann müsste sich allerdings nochmal jemand die .gif-Datei vornehmen...

-- Peter Steinberg 23:24, 22. Mai 2006 (CEST)

Auch wenn die Animation schön aussieht, ist eine übersicht mit den einzelnen Schritten leichter zu lesen. Bei Gelegenheit werde ich meinen Vorschlag vorstellen. Im Endeffekt braucht man je ein Bilde, in dem die Vielfachen von 2, 3, 5, usw. markiert sind. --Squizzz 23:52, 22. Mai 2006 (CEST)

Gut erkannt - es in Tat unglaublich wie ein derart simples Verfahren derart unsinnig langatmig erklärt werden kann. Auch die jetzige Fassung ist wieder ziemlich langatmig geraten und hängt sich viel zu stark an möglichen Verbessungen des Verfahrens auf ohne zunächst einmal das wirklich einfache Prinzip zu erklären. Es ist auch erstaunlich, dass diese einfache Verfahren als eine Art Allzweckwaffe zur Lösung schwieriger Probleme (siehe z.B. Quadratisches Sieb) verkauft wird. Benutzer:Fsswsb 25.05.2006 (falsch signierter Beitrag von Fsswsb (Diskussion | Beiträge) 13:00, 25. Mai 2006 (CEST))

Bild weiter beschleunigen

Also wenn die derzeit (30.04.08) dargestellte Animation "schnell" sein soll, wie langsam war dann erst die Alte. Man schläft ja förmlich vor der Animation ein. Sie ist viel zu langatmig und zäh. Die englische Version ist fast drei mal so schnell und man versteht den Sinn genauso. An wichtigen Stellen innerhalb der Animation wird auch diese Version etwas langsamer (zum besseren Verständnis). Ich wäre dafür die deutsche Version des Sieb des Eratosthenes zu beschleunigen. --Diktator 13:03, 30. Apr. 2008 (CEST)

 Kontra Vergiß nicht, Du bist (höchstwahrscheinlich ;-) mit der Materie vertraut. Mir persönlich ist die Grafik jetzt auch zu langsam. Aber wäre sie so schnell wie die in der englischsprachigen WP, hätte es mir arge Mühe bereitet, ihr zu folgen, als ich den Artikel das erste Mal las und ich vom Thema nur das Lemma kannte. Will sagen: so ist die Geschwindigkeit in Ordnung, denn wir wollen ja "Neulingen" Unbekanntes erklären und nicht uns selbst unterhalten (im Sinne von Fernsehersatz). --Carbenium 09:19, 2. Mär. 2009 (CET)

Programmcode fehlerhaft?

Ich bin mir grad nicht sicher, aber könnte es sein, dass der Programmcode in Zeile 11 an Stelle von "while i*i <= N" "while i <= N" heißen müsste? Denn so, wie es jetzt da steht, werden im Beispiel nur Zahlen bis 10 (100 <= 120) auf ihrem Primzahleigenschaft untersucht... -- ANONYM 15:17, 16. Sept. 2008 (CEST) (falsch signierter Beitrag von 132.199.134.33 (Diskussion) 15:18, 16. Sep. 2008 (CEST))

Sieb des Eratosthenes#Demonstration erklärt, warum es so, wie es im Artikel steht (also "while i*i <= N"), richtig ist. --Carbenium 09:24, 2. Mär. 2009 (CET)

»Es genügt … mit dem Quadrat der Primzahl zu beginnen … «

» … da alle kleineren Vielfachen bereits markiert sind.« Warum sie bereits markiert sind, kann man sich denken, aber vielleicht könnte man’s doch noch andeutungsweise erklären. Vielleicht kann das wer in einem knackig kurzen Satz dazuschreiben? – Fritz Jörn (Diskussion) 12:09, 20. Feb. 2013 (CET)

Optimiertes Verfahren

Optimiertes Verfahren: Es werden nur die bisher nicht markierten Vielfachen einer Primzahl markiert Das mag für die Animation eine Optimierung sein, aber im eigentlichen Verfahren ist die Sonderbehandlung eines bereits markierten Feldes aufwendiger, als es einfach doppelt zu markieren --Rat (Diskussion) 13:39, 21. Jun. 2015 (CEST)

Stimmt auffallend!

a = true ;

ist allemal effizienter als

if (a == false)
    a = true ;

Alte Rocker- und Programmiererweisheit: "einfach zuschlagen, ohne vorher Fragen zu stellen" --Carl B aus W (Diskussion) 12:05, 22. Jan. 2021 (CET)

"Da ein Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss"

Das ist falsch:

3*7 = 21

Die Primfaktoren sind also 3 und 7, sqrt( 21) aber ist ca. 4.58

3 < 4.58 < 7

=> 7 ist grösser als die Wurzel

Gruß (nicht signierter Beitrag von 176.0.106.64 (Diskussion) 23:52, 25. Jun. 2015 (CEST))

Die Formulierung lautet "Da EIN Primfaktor einer zusammengesetzten Zahl immer kleiner gleich der Wurzel der Zahl sein muss". Das heißt nicht, dass alle Primfaktoren kleiner sein müssen. --GDK Δ 11:31, 29. Jun. 2015 (CEST)

hab ein mindestens ergänzt. Dann betont man automatisch richtig. --Rat (Diskussion) 13:36, 30. Jun. 2015 (CEST)

Namensgeber oder Erfinder?

Siehe dazu Diskussion:Eratosthenes#Sieb, Diskussion am besten dort führen.--Kmhkmh (Diskussion) 01:33, 12. Okt. 2015 (CEST)

Laufzeit

Ich denke es sollte erwähnt werden welchen Laufzeitverhalten das Verfahren hat?

Gelber Kasten

Welchen Sinn hat der nervige gelbe Kasten am Anfang der Diskussionsseite, der seit 14 Jahren da steht?--Anaxagoras13 (Diskussion) 11:38, 22. Sep. 2020 (CEST)

Das ist doch nur eine Antwort auf einen Diskussionsbeitrag vom gleichen Tag und hätte einfach unter diesen gehört.--Anaxagoras13 (Diskussion) 11:48, 22. Sep. 2020 (CEST)

Hab ich jetzt mal entfernt, das Ding. -- Evilninja (Diskussion) 12:38, 22. Sep. 2020 (CEST)

Er war nicht entfernt, er stand nur woanders :-) Hab ihn mal entgelbt und hinter den Diskussionsbeitrag geschoben, für den er gedacht war.--Anaxagoras13 (Diskussion) 17:18, 22. Sep. 2020 (CEST)

lässt sich optimieren

"Das Verfahren lässt sich optimieren, wenn nur die ungeraden Zahlen darin abgespeichert werden." Das Weglassen der geraden Zahlen ist doch nichts anderes, als das erste Aussieben, bei dem die Vielfachen der ersten gefundenen Primzahl (2) durchs Sieb fallen. --Carl B aus W (Diskussion) 19:12, 21. Jan. 2021 (CET)

Das ist eben die Optimierung mit der man gegenüber dem ursprünglichen Algorithmus den Speicherverbrauch halbiert, das Rausstreichen beschleinigt und zudem ersten Schritt weglassen kann.--Kmhkmh (Diskussion) 01:31, 22. Jan. 2021 (CET)

Das Weglassen jeder zweiten Zahl ist nicht eine Optimierung, die sich im 21. Jahrhundert ein schlauer Wikipedianer ausgedacht hat, es IST genau der erste Schritt des Algorithmus, den der alte Grieche erfunden hat. --Carl B aus W (Diskussion) 11:52, 22. Jan. 2021 (CET)

Steht da irgendwo, dass es eine Erfindung eines Wikipedianers aus dem 21. Jahrhundert ist? Es ist halt eine Anmerkung zur Optimierung der "naiven" Implementierung des Algorithmus.--Kmhkmh (Diskussion) 01:15, 23. Jan. 2021 (CET)

Nö, da steht kein Beleg, wer die angebliche Optimierung erfunden hat. Dann wird's wohl ein Wikipedianer gewesen sein. --Carl B aus W (Diskussion) 03:02, 23. Jan. 2021 (CET)

Dann kann man auch gleich alle Vielfachen von 3 weglassen (also den zweiten Schritt des Verfahrens durchführen), das spart nochmal Speicherplatz. Und wenn wir schon dabei sind, dann auch gleich alle Vielfachen von 5,7,11,...

93.245.118.67 11:41, 14. Nov. 2023 (CET)