Informatik 10

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.

===== Lösung zu Aufgabe 3 (Zusatzaufgaben): Das Sieb des Eratosthenes =====
Schreibe ein Programm, das die Primzahlen bis 100 000 mit Hilfe des Sies des Eratosthenes ermittelt und ausgibt! \\ \\ 
Erweitere das Programm so,
  * a) dass der Benutzer zu Beginn eingeben kann, bis zu welcher Obergrenze die Primzahlen gesucht werden sollen.
  * b) dass es nach der Ermittlung der Primzahlen alle Primzahlzwillinge im Feld sucht und ausgibt.

<HTML>

<div class="java-online" style="height: 600px; width: 100%" data-java-online="{'withBottomPanel': false, 'id': 'eratosthenes2'}">

<script type="text/plain" title="Eratosthenes.java">
int anzahl = Input.readInt("Obere Grenze: ");

SystemTools.setSpeed(-1);
boolean[] gestrichen = new boolean[anzahl + 1];
// ... sind am Anfang alle mit false initialisiert!
// gestrichen[0] wird nicht benutzt!

// 1 streichen:
gestrichen[1] = true;

int p = 2;
while(p <= Math.sqrt(anzahl)) {
   // Vielfache streichen:
   for(int zuStreichen = p * 2; zuStreichen <= anzahl; zuStreichen = zuStreichen + p) {
      gestrichen[zuStreichen] = true;
   }
   
   // nächste nicht-gestrichene suchen:
   p++;
   while(gestrichen[p] == true && p <= anzahl) {
      p++;
   }

}

// Ausgabe:
for(int i = 1; i <= anzahl; i++) {
   if(gestrichen[i] == false) {
      println(i);
   }
}

// Ausgabe der Primzahlzwillinge:
for(int i = 3; i <= anzahl - 2; i++) {
   if(gestrichen[i] == false && gestrichen[i + 2] == false) {
      println("[" + i + ", " + (i + 2) + "]");
   }
}

</script>

</div>

</HTML>