Einführungskurs/Das Sieb des Eratosthenes
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Javascript</language>
== 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.<br />
Auf ihn geht aber auch ein interessanter Algorithmus zur Bestimmung aller ''Primzahlen'' zurück.<br />
=== Algorithmus ===
* Notiere die natürlichen Zahlen, beginne mit $2$.
<blockquote>
$2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...$
</blockquote>
* Unterstreiche die $2$ und streiche alle Vielfachen von $2$.
<blockquote>
$\underline{2}, 3, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, 9, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, 15, \cancel{16} 17, \cancel{18}, 19, \cancel{20}, ...$
</blockquote>
* Unterstreiche die erste freie Zahl (in diesem Falle die Zahl $3$) und streiche deren Vielfachen.
<blockquote>
$\underline{2}, \underline{3}, \cancel{4}, 5, \cancel{6}, 7, \cancel{8}, \cancel{9}, \cancel{10}, 11, \cancel{12}, 13, \cancel{14}, \cancel{15}, \cancel{16}, 17, \cancel{18}, 19, \cancel{20}, ...$
</blockquote>
* Verfahre mit allen weiteren freien Zahlen ebenso.
<blockquote>
$\underline{2}, \underline{3}, \cancel{4}, \underline{5}, \cancel{6}, \underline{7}, \cancel{8}, \cancel{9}, \cancel{10}, \underline{11}, \cancel{12}, \underline{13}, \cancel{14}, \cancel{15}, \cancel{16}, \underline{17}, \cancel{18}, \underline{19}, \cancel{20}, ...$
</blockquote>
* Alle unterstrichenen Zahlen sind Primzahlen.
=== Lösungsidee ===
* Belege ein eindimensionales Feld (''Array'') mit <math>n</math> ganzen Zahlen. Beginne mit der <math>2</math>.
* Setze die Vielfachen jedes der von Null verschiedenen Feldelemente auf Null. Beginne ebenfalls bei <math>2</math>.
* Gib nur die Feldelemente aus, die von Null verschieden sind.
=== Implementation ===
<code id="4d21a5984b92">
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;
}
</code>
<check id="check-172acda740ee9b4b0b1ef2d082f567b48b680ba0627b4d1974d6f188cf99722c">
PrimAusgabe(PrimSieb(10));
return (consoleLog == "2, 3, 5, 7, ") || (consoleLog == "2, 3, 5, 7");
</check>
<run id="4d21a516d111c">
PrimAusgabe(PrimSieb(1000));
</run>
=== Aufgaben ===
<ol>
<li>
Diskutieren Sie ausführlich, ob sich der intuitive Algorithmusbegriff auf das "Sieb des Eratosthenes" anwenden lässt.
</li>
<li>
Untersuchen Sie die Effizienz Ihrer Implementation.
</li>
</ol>