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>