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 <math>2</math>.

<blockquote>
<math>2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...</math>
</blockquote>

* Unterstreiche die <math>2</math> und streiche alle Vielfachen von <math>2</math>.

<blockquote>
<math>\usepackage{ulem} \uline{2}, 3, \xout{4}, 5, \xout{6}, 7, \xout{8}, 9, \xout{10}, 11, \xout{12}, 13, \xout{14}, 15, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>

* Unterstreiche die erste freie Zahl (in diesem Falle die Zahl <math>3</math>) und streiche deren Vielfachen.

<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, 5, \xout{6}, 7, \xout{8}, \xout{9}, \xout{10}, 11, \xout{12}, 13, \xout{14}, \xout{15}, \xout{16}, 17, \xout{18}, 19, \xout{20}, ...</math>
</blockquote>

* Verfahre mit allen weiteren freien Zahlen ebenso.

<blockquote>
<math>\usepackage{ulem} \uline{2}, \uline{3}, \xout{4}, \uline{5}, \xout{6}, \uline{7}, \xout{8}, \xout{9}, \xout{10}, \uline{11}, \xout{12}, \uline{13}, \xout{14}, \xout{15}, \xout{16}, \uline{17}, \xout{18}, \uline{19}, \xout{20}, ...</math>
</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>
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>
Einführungskurs/Das Sieb des Eratosthenes

Suche
