Das Sieb des Eratosthenes

Aus ProgrammingWiki

Inhaltsverzeichnis

1 Das Sieb des Eratosthenes

Das Sieb des Eratosthenes

Der griechische Mathematiker, Geograph, Philosoph, Philologe und Dichter Eratosthenes von Kyrene (* zwischen 276 und 273 v. Chr.; † um 194 v. Chr.) war der erste Gelehrte der Antike, der durch eine wissenschaftlich fundierte Messung den Umfang der Erde mit erstaunlicher Genauigkeit bestimmt hat.
Auf ihn geht aber auch ein interessanter Algorithmus zur Bestimmung aller Primzahlen zurück.

Algorithmus

Notiere die natürlichen Zahlen, beginne mit $LaTeX: 2$ .

$LaTeX: 2%2C%203%2C%204%2C%205%2C%206%2C%207%2C%208%2C%209%2C%2010%2C%2011%2C%2012%2C%2013%2C%2014%2C%2015%2C%2016%2C%2017%2C%2018%2C%2019%2C%2020%2C%20...$

Unterstreiche die $LaTeX: 2$ und streiche alle Vielfachen von $LaTeX: 2$ .

$LaTeX: %5Cusepackage%7Bulem%7D%20%5Culine%7B2%7D%2C%203%2C%20%5Cxout%7B4%7D%2C%205%2C%20%5Cxout%7B6%7D%2C%207%2C%20%5Cxout%7B8%7D%2C%209%2C%20%5Cxout%7B10%7D%2C%2011%2C%20%5Cxout%7B12%7D%2C%2013%2C%20%5Cxout%7B14%7D%2C%2015%2C%20%5Cxout%7B16%7D%2C%2017%2C%20%5Cxout%7B18%7D%2C%2019%2C%20%5Cxout%7B20%7D%2C%20...$

Unterstreiche die erste freie Zahl (in diesem Falle die Zahl $LaTeX: 3$ ) und streiche deren Vielfachen.

$LaTeX: %5Cusepackage%7Bulem%7D%20%5Culine%7B2%7D%2C%20%5Culine%7B3%7D%2C%20%5Cxout%7B4%7D%2C%205%2C%20%5Cxout%7B6%7D%2C%207%2C%20%5Cxout%7B8%7D%2C%20%5Cxout%7B9%7D%2C%20%5Cxout%7B10%7D%2C%2011%2C%20%5Cxout%7B12%7D%2C%2013%2C%20%5Cxout%7B14%7D%2C%20%5Cxout%7B15%7D%2C%20%5Cxout%7B16%7D%2C%2017%2C%20%5Cxout%7B18%7D%2C%2019%2C%20%5Cxout%7B20%7D%2C%20...$

Verfahre mit allen weiteren freien Zahlen ebenso.

$LaTeX: %5Cusepackage%7Bulem%7D%20%5Culine%7B2%7D%2C%20%5Culine%7B3%7D%2C%20%5Cxout%7B4%7D%2C%20%5Culine%7B5%7D%2C%20%5Cxout%7B6%7D%2C%20%5Culine%7B7%7D%2C%20%5Cxout%7B8%7D%2C%20%5Cxout%7B9%7D%2C%20%5Cxout%7B10%7D%2C%20%5Culine%7B11%7D%2C%20%5Cxout%7B12%7D%2C%20%5Culine%7B13%7D%2C%20%5Cxout%7B14%7D%2C%20%5Cxout%7B15%7D%2C%20%5Cxout%7B16%7D%2C%20%5Culine%7B17%7D%2C%20%5Cxout%7B18%7D%2C%20%5Culine%7B19%7D%2C%20%5Cxout%7B20%7D%2C%20...$

Alle unterstrichenen Zahlen sind Primzahlen.

Lösungsidee

Belege ein eindimensionales Feld (Array) mit $LaTeX: n$ ganzen Zahlen. Beginne mit der $LaTeX: 2$ .
Setze die Vielfachen jedes der von Null verschiedenen Feldelemente auf Null. Beginne ebenfalls bei $LaTeX: 2$ .
Gib nur die Feldelemente aus, die von Null verschieden sind.

Implementation

public void PrimAusgabe(int[] liste) { int zaehler = 0; for (int i = 0; i < liste.length; i++) if (liste[i] != 0) { zaehler++; if (zaehler%15 == 0) System.out.println(liste[i]+", "); else System.out.print(liste[i]+", "); } } public int[] PrimSieb(int n) { int[] liste = new int[n]; // Implementation des Algorithmus return liste; }

Quelltext überprüfen:

PrimAusgabe(PrimSieb(1000));

Aufgaben

Diskutieren Sie ausführlich, ob sich der intuitive Algorithmusbegriff auf das "Sieb des Eratosthenes" anwenden lässt.
Untersuchen Sie die Effizienz Ihrer Implementation.

Das Sieb des Eratosthenes

Aus ProgrammingWiki

Inhaltsverzeichnis

Das Sieb des Eratosthenes

Algorithmus

Lösungsidee

Implementation

Aufgaben

Ansichten

Persönliche Werkzeuge

Navigation

Suche

Werkzeuge