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 (Sternchenaufgabe): Das Sieb des Eratosthenes =====
Schreibe ein Programm, das die Primzahlen bis 100 000 mit Hilfe des Sies des Eratosthenes ermittelt und ausgibt! \\ \\ 
**Strategie:**
  * Deklariere ein Feld ''gestrichen'' von 100 001 Werten des Datentyps ''boolean''. ''gestrichen[i]'' soll angeben, ob das Zahlenfeld mit der Zahl ''i'' "gestrichen" ist.
  * Setze ''gestrichen[0] = true'' und ''gestrichen[1] = true'', denn 0 und 1 sind keine Primzahlen
  * Jetzt bis Du dran! Hier noch ein paar kleine Tipps:
    * Du wirst zwei ineinandergeschachtelte Wiederholungen brauchen.
    * Die Wurzel von 100 000 erhältst Du so: ''Math.sqrt(100000)''


<HTML>

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

<script type="text/plain" title="Eratosthenes.java">
int anzahl = 100000;

boolean[] gestrichen = new boolean[anzahl + 1];
gestrichen[0] = true;
gestrichen[1] = true;

for(int i = 2; i <= anzahl; i++) {
   gestrichen[i] = false;
}

int nächstePrimzahl = 2;
while(nächstePrimzahl <= Math.sqrt(anzahl)) {
   // Alle Vielfachen von nächstePrimzahl streichen:
   println("Streiche die Vielfachen von " + nächstePrimzahl + "...");
   for(int i = nächstePrimzahl * 2; i <= anzahl; i = i + nächstePrimzahl) {
      gestrichen[i] = true; 
   }
   
   // nächste Primzahl finden
   nächstePrimzahl++;
   while(gestrichen[nächstePrimzahl]) {
      nächstePrimzahl++;
   }
}

// Ausgabe der Primzahlen
int spalte = 0;
for(int i = 2; i <= anzahl; i++) {
   if(gestrichen[i] == false) {
      print(i + ", ");
      spalte++;
      if(spalte == 5) {   // Zeilenumbruch nach jeweils 5 Spalten
         println();
         spalte = 0;
      }
   }
}
</script>

</div>

</HTML>

===== Weitere Variante (mit while-loop anstatt for-loop) =====

<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 = 100000;

boolean[] gestrichen = new boolean[anzahl + 1];
gestrichen[0] = true;
gestrichen[1] = true;

for(int i = 2; i <= anzahl; i++) {
   gestrichen[i] = false;
}

int nächstePrimzahl = 2;
while(nächstePrimzahl <= Math.sqrt(anzahl)) {
   // Alle Vielfachen von nächstePrimzahl streichen:
   println("Streiche die Vielfachen von " + nächstePrimzahl + "...");
   int i = nächstePrimzahl * 2;
   while (i <= anzahl) {
      gestrichen[i] = true; 
      i = i + nächstePrimzahl;
   }
   
   // nächste Primzahl finden
   nächstePrimzahl++;
   while(gestrichen[nächstePrimzahl]) {
      nächstePrimzahl++;
   }
}

// Ausgabe der Primzahlen
int spalte = 0;
for(int i = 2; i <= anzahl; i++) {
   if(gestrichen[i] == false) {
      print(i + ", ");
      spalte++;
      if(spalte == 5) {   // Zeilenumbruch nach jeweils 5 Spalten
         println();
         spalte = 0;
      }
   }
}
</script>

</div>

</HTML>