Archive for Februar 26th, 2016

 

Mathe-Magie: Sieb des Eratosthenes

Primzahlsieb oder Lambdoma ?

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):

Primzahlsieb

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 Artikel 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.

 

Posted by on Februar 26th, 2016 Kommentare deaktiviert