Das Sieb des Eratosthenes

Aus ProgrammingWiki

Inhaltsverzeichnis 1 Das Sieb des Eratosthenes 1.1 Algorithmus 1.2 Lösungsidee 1.3 Implementation 1.4 Aufgaben

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 .

• Unterstreiche die und streiche alle Vielfachen von .

• Unterstreiche die erste freie Zahl (in diesem Falle die Zahl ) und streiche deren Vielfachen.

• Verfahre mit allen weiteren freien Zahlen ebenso.

• Alle unterstrichenen Zahlen sind Primzahlen.

Lösungsidee

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

Implementation

function PrimAusgabe(liste) { var zaehler = 0; var s = ""; for (var i = 0; i < liste.length; i++) if (liste[i] != 0) { zaehler++; if (zaehler%15 == 0) { console.log(s); s = ""; // reset s } else s+= (liste[i]+", "); } console.log(s); } function PrimSieb(n) { var liste = []; // Implementation des Algorithmus return liste; }

PrimAusgabe(PrimSieb(1000));

ausführen

Aufgaben

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