Mathemagie:
Sieb des Eratosthenes

erathostene1s Primzahlsieb oder Lambdoma ?
Sierpinski Enigma ©scrano 2014

Grundprinzip

Das Sieb des Eratosthenes basiert auf der Eigenschaft, dass jede natürliche Zahl entweder eine Primzahl oder das Vielfache einer solchen ist. Zunächst werden alle Natürlichen Zahlen des gewünschten Intervalls in einer Liste aufgeschrieben:

Nun werden, bei 2 beginnend, alle Vielfachen der jeweils niedrigsten Zahl aus der Liste gestrichen (Diese können ja keine Primzahlen sein, da sie Vielfache der niedrigsten Zahl sind): Hat man dieses Verfahren oft genug durchgeführt, so bleiben am Ende nur noch die Primzahlen übrig (diese werden niemals gestrichen, da sie nicht vielfache irgendeiner kleineren Zahl sind):

zzzz Prinzip des Primzahl-Siebs.

Optimierung des Prinzips

Dieses Verfahren lässt sich jedoch noch deutlich optimieren, beachtet man folgende zwei Regeln:

  • Die kleinste Zahl, die als Vielfaches einer Primzahl gestrichen wird ist ihr Quadrat. Alle niedrigeren Vielfache sind bereits gestrichen, da sie auch Vielfache einer kleineren Primzahl sind. Die größte Zahl deren Vielfache noch gestrichen werden müssen ist die Wurzel der höchsten Zahl des Intervalls, in unserem Beispiel:
  • Damit sind wir in diesem Beispiel, dem Intervall von 2 bis 50 bereits nach 4 Schritten fertig! Es sind nur die Vielfachen von 2, 3, 5 und 7 zu streichen.

Einen Artikel über die Verwendung des Pythagoräischen Lambdoma, das eine Verwandtschaft mit diesem Verfahren aufweist als Primzahlsieb, werde ich demnächst einstellen. Hierzu fand ich einen interessanten Beitrag auf der Seite „tetraktys.de„, welcher diese Idee verfolgt. Auch Tetraktys und Lambdoma allgemein, ihr Bezug zur Musiktheorie und Harmonik, werden noch Gegenstand einiger Posts sein.

 

The Eagle has landed …

on your PCB-project!

Freeware | Get the EAGLE Light Edition free | CadSoft EAGLE

Stauferr-Adler am Kloster Lorch. ©beast666 2016
Staufer-Adler am Kloster Lorch. ©beast666 2016

Download the free version of EAGLE PCB Software and start designing your own circuits. The Freeware is available for Windows, Mac OS X and Linux.
View on www.cadsoftusa.com

Freie Routing-und Design/Layout Software für das eigene PCB-Projekt – z.B. für Arduino oder Raspberry PI.