| 5.2 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.3 | |
| zur Starseite | www.pohlig.de (C) MPohlig 2002 |