6.12.4 Das Sieb des Erathostenes (Implementierung)
 
Der Algorithmus Der Algorithmus: Sieb des Erathostenes ist uns schon früher begegnet. Wenn man sich nicht mehr genau erinnert, schaue man dort noch einmal nach.
Algorithmus: Sieb des Erathostenes

 
Download:
Erathostenes.java

 

import info1.*;
public class Erathostenes {
  public static void main(String[] args) {
    System.out.print("Bis zu welcher Zahl soll auf prim 
                      geprueft werden? ");
    int max = Console.in.readInt();
    boolean[] primzahlen;
    primzahlen = new boolean[max];
    //Initialisierungsschleife
    for (int n = 2; n < primzahlen.length; n++) {
      primzahlen[n] = true;
    }
    //Sieb
    for (int n = 2; n < Math.sqrt(primzahlen.length);n++) {
      if(primzahlen[n]) {
        for (int i = 2*n; i < primzahlen.length; i += n) {
          primzahlen[i] = false;
        }
      }
    }
   //Ausgabe
    for ( int n = 2; n < primzahlen.length; n++) {
      if (primzahlen[n]) {
         System.out.println(n);
      }
    }
  }
}
Bemerkung Wir benutzen die Indizes des Feldes als die Zahlen, die dahingehen untersucht werden sollen, ob sie Primzahlen sind oder nicht. Die boolschen Werte true und false geben darüber Auskunft. Das rot-Färben der Zahlen in 6.3 entspricht dem 'true'-Setzen in unserem Programm. Entsprechend wird das Streichen der Vielfachen, also das Schwärzen in 6.3 durch das  'false'-setzen realisiert. Die Indizes der Stellen, wo zum Schluss ein true übrigbleibt sind die gesuchten Primzahlen.
 
zu 6.12.5 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2007