Netz des Eratosthenes

Netz des Eratosthenes

Das Sieb des Eratosthenes ist ein Algorithmus zur Bestimmung einer Liste oder Tabelle aller Primzahlen kleiner oder gleich einer vorgegebenen Zahl. Er ist nach dem griechischen Mathematiker Eratosthenes von Kyrene benannt.

Inhaltsverzeichnis

Funktionsweise

Zunächst werden alle Zahlen 2, 3, 4,… bis zu einem frei wählbaren Maximalwert S aufgeschrieben. Die zunächst unmarkierten Zahlen sind potentielle Primzahlen. Die kleinste unmarkierte Zahl ist immer eine Primzahl. Nachdem eine Primzahl gefunden wurde, werden alle Vielfachen dieser Primzahl als zusammengesetzt markiert. Es genügt dabei, mit dem Quadrat der Primzahl zu beginnen, da alle kleineren Vielfachen bereits markiert sind. Sobald das Quadrat der Primzahl größer als die Schranke S ist, sind alle Primzahlen kleiner oder gleich S bestimmt: Es sind die nicht markierten Zahlen.

Das Verfahren beginnt also damit, die Vielfachen 4, 6, 8,… der kleinsten Primzahl 2 durchzustreichen. Die nächste unmarkierte Zahl ist die nächst größere Primzahl, die 3. Anschließend werden deren Vielfache 9, 12, 15,… durchgestrichen, usw.

Das Sieb funktioniert auch (nur etwas langsamer), wenn immer alle Vielfachen (und nicht erst die ab der Quadratzahl) markiert werden. In dieser Form ist es bereits für Lernende der 6. Klasse verstehbar. In der Regel wird in dieser Altersstufe auch noch ein Stück über √S hinaus gearbeitet, bis sich die Erkenntnis aufdrängt, dass nun „nichts mehr passiert“.

Demonstration

Verfahren, wie die Primzahlen zwischen 2 und 120 ermittelt werden: Erst werden alle Vielfachen von 2 gestrichen, dann alle Vielfachen von 3, 5, und 7. Die Markierungen beginnen jeweils mit dem Quadrat der Primzahl: 4, 9, 25, 49. Da bereits 112 = 121 nicht mehr im Wertebereich liegt, werden ab 11 keine zusammengesetzten Zahlen mehr markiert; alle noch unmarkierten Zahlen sind prim.

Implementierung

Eine beispielhafte Implementierung des Algorithmus als Pseudocode:

const N = 10000
var gestrichen: array [2..N] of boolean

{ Initialisierung des Primzahlfeldes: }
{ Alle Zahlen im Feld sind zu Beginn nicht gestrichen. }
for i = 2 to N do
  gestrichen[i] = false
end

i = 2
while i*i <= N
do
  if not gestrichen[i]
  then
    // i ist prim, streiche seine Vielfache mit i*i beginnend:
    for j = i*i to N step i
    do
      gestrichen[j] = true
    end
  endif
  i = i+1
end

for i = 2 to N do
  if not gestrichen[i] then 
    print i; ", "; 
end

Das Verfahren lässt sich optimieren, wenn nur die ungeraden Zahlen darin abgespeichert werden. Es gibt zwar bessere Verfahren als das Sieb des Eratosthenes (z.B. das Sieb des Atkin), es ist allerdings immer noch optimal, wenn größere Zahlenbereiche nach Primzahlen abgesucht werden sollen.

Literatur

Weblinks


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Эратосфен — (Eratosthenes) греческий математик, астроном, географ и филолог (276 194 до Р. Х.), сын Эглаоса, уроженец Кирены. Прибыв в Александрию в раннем возрасте, он получил здесь образование под руководством своего ученого земляка Каллимаха, стоявшего во …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Эратосфен, математик — (Eratosthenes) греческий математик, астроном, географ и филолог (276 194 = до Р. Хр.), сын Эглаоса, уроженец Кирены. Прибыв в Александрию в раннем возрасте, он получил здесь образование под руководством своего ученого земляка Каллимаха, стоявшего …   Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона

  • Fluss Eridanus — Daten des Sternbildes Fluss Eridanus Deutscher Name Fluss Eridanus Lateinischer Name Eridanus Lateinischer Genitiv Eridani Lateinische Abkürzung Eri Rektaszension 1h 25m bis 5h 11m De …   Deutsch Wikipedia

  • Explizite Zuordnungsvorschrift — Als Folge wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das Objekt mit der… …   Deutsch Wikipedia

  • Potenzfolge — Als Folge wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das Objekt mit der… …   Deutsch Wikipedia

  • Sequenz (Mathematik) — Als Folge wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das Objekt mit der… …   Deutsch Wikipedia

  • Zahlenfolge — Als Folge wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das Objekt mit der… …   Deutsch Wikipedia

  • Geosemantik — (im Englischen ist der Begriff geospatial semantics üblich) ist ein interdisziplinäres Forschungsfeld und befasst sich mit der Bedeutung von Geoinformation. Die Vision des virtuellen Globus Inhaltsverzeichnis …   Deutsch Wikipedia

  • Eridanus (Sternbild) — Sternbild Fluss Eridanus …   Deutsch Wikipedia

  • Folge (Mathematik) — Als Folge oder Sequenz wird in der Mathematik eine Auflistung (Familie) von endlich oder unendlich vielen fortlaufend nummerierten Objekten (beispielsweise Zahlen) bezeichnet. Dasselbe Objekt kann in einer Folge auch mehrfach auftreten. Das… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”