Das Sieb des Eratosthenes

Wenn man den Titel so liest, werden sich wahrscheinlich die wenigstens etwas darunter vorstellen können…

Mir ging es genauso! Zuerst habe ich an Mathematik wie Satz des Pythagoras u.ä. gedacht, doch damit hat dies nun nicht viel zu tun, obwohl es um Mathematik, wenn auch einfache, geht!

Nun was ist dieses Sieb nun:

Das Sieb des Eratosthenes beschreibt ein Vorgang um aus einer Zahlenkette alle Primzahlen herauszulesen.

Eine Primzahl ist eine natürliche Zahl mit genau zwei natürlichen Zahlen als Teiler, nämlich der Zahl 1 und sich selbst

sponsored by Wikipedia

Eratosthenes macht sich dabei das Wissen zunutze, dass jede Nicht-Primzahl ein Vielfaches einer Primzahl ist. So wird jede zahl genommen und mit allen x-Reihen (2er-Reihe, 3er-Reihe, …, 1234er-Reihe) verglichen.

Gibt eine Zahl dann ein Positives Feedback, sprich sie ist ein Vielfaches einer andern, ist es keine Primzahl mehr und kann ausgeschlossen werden.

So kann man, wenn man genügend Rechenleistung hat, Primzahlen mit mehreren Millionen Stellen generieren lassen.

Der Code zum ganzen, habe ich in Java geschrieben. Er ist sicherlicht nicht gerade der kürzeste und beste, doch ich hoffe ihr verzeiht mir, wenn ich euch sage, dass ich gerade eben erst angefangen habe Java zu programmieren.

Ach ja: Programmiert wurde das ganze in Eclips unter Ubuntu 8.04 🙂

  • Lösungsbeispiel – TXT
  • Lösungsbeispiel – Java

Ein Kommentar bei „Das Sieb des Eratosthenes

  1. Ich glaube, diese Möglichkeit zur Anwendung der Mathematik wurde auch schon mal in einer Fernsehsendung präsentiert. Ich hatte es auch schon mal verstanden, nur wieder vergessen. Wenn man einmal im Stoff ist, lässt sich dieser Vorgang einfach einleiten. Nur die Einarbeitung in dieses Thema sieht so schrecklich aus … 😉

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.