einfache Version Sieb des eratosthenes

[ert009]

Hallo,
Ich muss eine Hausaufgabe erledigen in der es darum geht aus einen Feld alle Primzahlen mit Hilfe des Siebes von Eratstohones zu finden und die nicht-Primzahlen zu löschen.Ich habe jetzt schon mal ein Feld mit einer durch eine Variabel bestimmenenden Anzahl von Zahlen generiert, aber mein Problem ist es jetzt, darauf das S. von E.
Ich würde die kleinste Zahl quadrieren und dann nach Vielfachen der quadrierten Zahl suchen,die Vielfachen würde ich dann gleich null setzten und dann die zweitkleinste Zahl wieder quadrieren und dasselbe noch mal ausführen. Mein Problem ist jetzt wie implemtiere ich eine Methode die die kleinste Zahl im Feld such (Man könnte vll die Zahl mit den kleinsten Index nehmen)und die Vielfachen der Zahl glich null setzt.

public class sde
{
    private int [ ] zahlen;
 
  
 
     
  
     public void Feldgroesse(int x){
     
        zahlen = new int [x];
       
 
        zahlen[0]=2;      
        for (int i=2;i-1<x;i++){
      zahlen[i - 2] = i;
        }
    }
}

Also mein konkretes

 

[Antoras]

Schau dir das mal an, da ist sogar Pseudocode dabei: Sieb des Eratosthenes ? Wikipedia

 

[ert009]

Tut mir Leid ich versthe zwar was da steht aber irgendiwe wieß ich nicht wie ich es auf das Feld anwenden soll und wie ich dann die Zahlen ,die ja alle in einen Feld sien sollen gleich null setzen kann.

 

[Landei]

Erst mal brauchen wir ein Feld, aber nicht mit Zahlen, sondern mit boolean:

boolean[] prim = new boolean[1000]; //für Primzahlen bis 1000

Jetzt sind 0 und 1 per Definition keine Primzahlen, für alle anderen Zahlen nehmen wir es erst einmal an, solange niemand das Gegenteil beweist. Also füllen wir das Feld ab der Stelle 2 mit true:

for(int i = 2; i < prim.length; i++){
  prim[i] = true;
}

Jetzt gehen wir das Feld von vorn durch. Sobald wir eine Zahl haben, die true ist, ist es eine Primzahl, und wir setzen alle Vielfachen auf false:

for(int p = 0; p < prim.length; p++) {
   if (prim[p]) { //Primzahl gefunden
      for(int v = 2*p; v < prim.length; v = v + p) {
           prim[v] = false; //alle Vielfachen von p "wegstreichen"
      }
   }
}

Am Ende wollen wir natürlich alle Primzahlen ausgegeben haben:

for(int i = 0; i < prim.length; i++) {
   if (prim[i]) {
      System.out.println(prim[i]);
   }
}

Und wie du das jetzt in ein Programm bekommst, findest du sicher selbst heraus.

 

[ert009]

Danke für die Hilfe mien Programm funktioniert jetzt.Allerdings verstehe ich diesen Teil noch nicht,besonders die Zeilen 1-3.

for(int p = 0; p < prim.length; p++) {
   if (prim[p]) { //Primzahl gefunden
      for(int v = 2*p; v < prim.length; v = v + p) {
           prim[v] = false; //alle Vielfachen von p "wegstreichen"
      }
   }

 

[Landei]

Du gehst das Feld von vorne durch, bis du ein true findest, also p eine Primzahl ist. Bevor du weitergehst, musst du in einer weiteren Schleife alle Vielfachen von p wegstreichen, da das ja keine Primzahlen sind. Angenommen p ist 7. Dann ist das erste Vielfache v von p 2*7 = 14. Das nächste Vielfache ist 14 + 7 = 21. Das nächste 21 + 7 = 28 u.s.w. Wenn du mit dem Wegstreichen in der inneren Schleife fertig bist, geht es in der äußeren Schleife mit der nächsten Primzahl weiter.

Hier mal der Vorgang für ein kurzese Feld von 0 bis 15:

Ausgangszustand:
0123456789012345
FFTTTTTTTTTTTTTT
  ^ erste Primzahl ist 2

0123456789012345
FFTTFTFTFTFTFTFT <- Vielfache von 2 weggestrichen (4,6,8,10,12,14)

0123456789012345
FFTTFTFTFTFTFTFT 
   ^ zweite Primzahl ist 3     

0123456789012345
FFTTFTFTFFFTFTFF <- Vielfache von 3 weggestrichen (6,9,12,15)

0123456789012345
FFTTFTFTFFFTFTFF
     ^ dritte Primzahl ist 5

u.s.w.