DseWiki: SiebDesEratosthenes

Veränderung (letzte Korrektur) (Änderung, Normalansicht)

Verändert: 4c4

Eine natürliche Zahl ist prim, wenn sie exakt zwei natürliche Teiler hat, 1 und sich selbst. Ansonsten nennen wir die Zahl zusammengesetzt. Die Zahl 1 ist als einzige weder prim noch zusammengesetzt, wir sagen sie sei eine Einheit.

Eine natürliche Zahl ist prim, wenn sie exakt zwei natürliche Teiler hat, nämlich 1 und sich selbst. Ansonsten nennen wir die Zahl zusammengesetzt. Die Zahl 1 ist als einzige weder prim noch zusammengesetzt, wir sagen sie sei eine Einheit.

Verändert: 8c8

Eratosthenes dachte sich ein Sieb aus, mit dem man Primzahlen identifizieren kann. Ein Sieb ist wie ein Filter in das man nach dem Kochen Spaghettie gibt. Das wasser läuft durch das Sieb, die Spaghetties bleiben zurrück. [2] Das Sieb des Eratosthenes filtert Produkte aus, und lässt die PrimZahlen zurrück.

Eratosthenes dachte sich ein Sieb aus, mit dem man Primzahlen identifizieren kann. Ein Sieb ist wie ein Filter in das man nach dem Kochen Spaghettie gibt. Das Wasser läuft durch das Sieb, die Spaghetties bleiben zurück. [2] Das Sieb des Eratosthenes filtert Produkte aus, und lässt die PrimZahlen zurück.

Verändert: 60c60

[1] Was bitteschön ist denn "genau abschätzen"?

[1] Was bitteschön ist denn "genau abschätzen"? -- BodoThiesen

Verändert: 62c62

[2] Ist es eigentlich in allen englischen Texten so, daß allgemein bekannte Wörter wie Filter erklärt werden?

[2] Ist es eigentlich in allen englischen Texten so, daß allgemein bekannte Wörter wie Filter erklärt werden? -- BodoThiesen

Frei aus dem Englischen übersetzt von BodoThiesen.

Das Sieb des Eratosthenes

Eratosthenes von Cyrene (276-194 v.Chr.) war der erste, der den Durchmesser der Erde genau abgeschätzt[1] hat. Einige Jahrzehnte lang war er Direktor der berühmtesten Bibliothek Alexandrias. Er war ein hoch angesehener Mann, aber bedauerlicherweise sind nur noch Fragmente seiner Arbeit vorhanden.

Erstelle eine Liste mit allen ganzen Zahlen kleiner oder gleich n (und größer als 1). Streiche alle Vielfache von Primzahlen kleiner oder gleich der Quadratwurzel von n aus. Dann sind alle übrigen Zahlen PrimZahlen.

Beachte daß, wenn ein Teiler eines Faktors größer als die Quadratwurzel ist, der andere Faktor kleiner als die Quadratwurzel sein wird. Daher müssen keine Vielfache von Primzahlen größer als die Quadratwurzel von n beachtet werden.

Als Beispiel: Um alle PrimZahlen kleiner 50 zu finden, zuerst alle Zahlen von 2 bis 50 auflisten. (Und schon haben wir den berühmten 0-1 Fehler. -- BodoThiesen)

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 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Die erste Zahl 2 ist eine PrimZahl, also behalte sie und markiere die Vielfachen.

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 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Die erste übrig gebliebene Zahl ist 3, es ist die erste ungerade PrimZahl. Überspringe sie, und markiere alle Vielfachen von ihr. Zahlen wie 6, 12 wurden bereits (als Vielfache von 2) markiert, aber das stört nicht weiter.

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 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Die nächste übrig gebliebene Zahl ist die 5, die zweite ungerade PrimZahl. Überspringe sie, und markiere alle Vielfachen von ihr (25 und 35 sind die einzigen, die noch nicht markiert waren).

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 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Die nächste übrig gebliebene Zahl ist die 7, die dritte ungerade PrimZahl. Überspringe sie, und markiere alle Vielfachen von ihr (49 ist die einzige, die noch nicht markiert war).

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 37 38 39 40

41 42 43 44 45 46 47 48 49 50

Die nächste übrig gebliebene Zahl, die 11, ist größer als die QuadratWurzel? von 50, daher sind alle übrigen unmarkierten Zahlen PrimZahlen. Kannst Du nachvollziehen, warum?

Die PrimZahlen kleiner 50 sind: 2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47 wie oben ersichtlich. Beachte, daß wir diese Primzahlen ohne Dividieren zu müssen herausgefunden haben.

[1] Was bitteschön ist denn "genau abschätzen"? -- BodoThiesen

[2] Ist es eigentlich in allen englischen Texten so, daß allgemein bekannte Wörter wie Filter erklärt werden? -- BodoThiesen

Links:

http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm (englischer Originaltext)

KategorieAlgorithmus