5.3 Das Sieb des Erathostenes
 
Ausführliches Beispiel:
Das Sieb des Erathostenes		 Problemspezifikation:
Bestimme die Primzahlen in dem Intervall [1..n].

Algorithmenidee in Umgangssprache:
Schreibe die Zahlen 1 bis n nieder. Streiche daraus die Vielfachen von 2, 3, 5 usw. bis zur Quadratwurzel aus n. Die nicht gestrichenen Zahlen sind die Primzahlen. (Wir sprechen von einer Algorithmusidee, weil das Wörtchen "usw." beim Formulieren eines Algorithmus eigentlich nicht auftauchen darf. Warum?)

Ausfühung für n=36

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 [die Vielfachen von 2 sind gestrichen]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 [die Vielfachen von 3 sind gestrichen]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 [die Vielfachen von 5 sind gestrichen]
  Können Sie den Algorithmus in der Normsprache niederschreiben? Schicken Sie mir die Lösung
 
zu 5.4 Übungen
zu  
zur Startseite www.pohlig.de  (C) MPohlig 2007