Site hosted by Angelfire.com: Build your free website today!

Sieb des Eratosthenes


Das Sieb des Eratosthenes ist ein effizienter Algorithmus zum Herausfinden aller vorhandenen Primzahlen im Bereich von 2 bis zur Obergrenze N. Er funktioniert folgendermaßen:
In einem boolschen Feld werden zunächst alle N Elemente auf true gesetzt, was hier soviel heißt, wie "noch im Feld vorhanden".
Dann werden alle Vielfachen der Primzahl 2 auf false gesetzt, da sie ja durch 2  teilbar sind. Danach wird das nächste Element, das noch "true" ist hergenommen und alle seine Vielfachen gestrichen. Das ganze wird solange wiederholt, bis der Teiler die Grenze von sqrt(N) überschreitet. Alle i, bei denen nach Ablauf des Algorithmus feld[i] gleich true gilt, sind Primzahlen.


Die Implementierung mit einem boolschen Feld 
void cm_SiebDesEratosthenes(const UL N, bool feld[]) {
     for(UL i=2; i<=N; ++i) {
         feld[i] = true;
     }

     for(i=2; i*i<=N; ++i) {     // nächste Primzahl 
         if(feld[i]==true)
             for(UL j=i+i; j<=N; j+=i) {
                 feld[j] = false;     // alle Vielfachen dieser Primzahl streichen
             }
     }
}

Es muss vor der Funktionsdefinition noch (wie im folgenden Listing zu sehen) mit typedef unsigned long UL; UL als äquivalent zu unsigned long bekannt gemacht werden.

Arbeitsweise in einem lauffähigen Programm 
#include <iostream.h>

typedef unsigned long UL;

void cm_SiebDesEratosthenes(const UL N, bool feld[]);

int main() {
     const UL N = 1000000;
     bool feld[N+1];
     cm_SiebDesEratosthenes(N, feld);
     UL anzahl = 0;
     for(UL i=2; i<N; ++i) {     // Ausgeben der Primzahlen
         if(feld[i] == true) {
             anzahl++;
             cout << "     " << i;
             if(anzahl % 5 == 0) cout << '\n';
         }
     }
     cout << "\n\n Im Bereich von 2 bis " << N << " befinden sich "
         << anzahl << " Primzahlen.\n";
     return 0;
}


void cm_SiebDesEratosthenes(const UL N, bool feld[]) {
     for(UL i=2; i<=N; ++i) {
         feld[i] = true;
     }

     for(i=2; i*i<=N; ++i) {     // nächste Primzahl 
         if(feld[i]==true) 
             for(UL j=i+i; j<=N; j+=i) {
                 feld[j] = false;     // alle Vielfachen dieser Primzahl streichen
             }
     }
}


   Computer    Programmieren (incl. C++ Kurs)    Algorithmen    Bücher    

Zeitschriften    Heavy Metal    Mountainbiking    Meine Katze    

Über mich und die Site    Links    Downloads    Gästebuch    HP mit Umfrage