Sieb Des Eratosthenes
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Frei aus dem Englischen übersetzt von BodoThiesen.

Das Sieb des Eratosthenes
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.

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.

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.

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)

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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.

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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).

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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).

 2345678910
11121314151617181920
21222324252627282930
31323334353637383940
41424344454647484950

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:


KategorieAlgorithmus
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 8. Oktober 2003 19:45 (diff))
Suchbegriff: gesucht wird
im Titel
im Text