Hilfe zu Sieb des Eratosthenes ohne boolean

[Zentriks]

Hallo, ich erkläre mal meine Situation. Ich nehme gerade an einem Informatikkurs, eher gesagt Java-Kurs teil, um mein Wissen für das Studium aufzufrischen. Bevor es zu meiner Frage kommt, werde ich erstmal alles reinschreiben, was ich bis jetzt bereits an Code geschrieben habe. Ich weiß, dass es hier Unmengen an Posts zu diesem Thema gibt. Dennoch habe ich nichts gefunden, dass mein Problem löst. Ich bin auch, denke ich ziemlich nah dran, fertig zu sein.

Uns wurde Code vorgegeben, sodass ich es ohne boolean, wie ich es verstehe, implementieren soll. Hier noch die Aufgabenstellung:

















Folgender Code wird mir vorgegeben:

class Prim {
    int[] primzahlenBestimmen(int n) {
        int[] zahlen = new int[n+1];

        // Zunaechst sind alle Zahlen nicht markiert
        for (int i = 0; i <= n; i++) {
            zahlen[i] = i;
        }

        // 0 und 1 sind keine Primzahlen, werden daher markiert
        zahlen[0] = 0;
        zahlen[1] = 0;

        // Fuegen Sie Ihre Implementierung hier ein.
        
        return zahlen;
    }
    
    public static void main(String[] args) {
        Prim prim = new Prim();
        
        int[] output = prim.primzahlenBestimmen(20);
        System.out.println("Die Primzahlen kleiner gleich 20 lauten:");
        // Mit der folgenden Zeile kann ein Feld testweise ausgegeben werden
        System.out.println(Arrays.toString(output));
    }
}

Diesen habe ich dann wie folgt erweitert:

class Prim {
    int[] primzahlenBestimmen(int n) {
        int[] zahlen = new int[n+1];

        // Zunaechst sind alle Zahlen nicht markiert
        for (int i = 0; i <= n; i++) {
            zahlen[i] = i;
        }

        // 0 und 1 sind keine Primzahlen, werden daher markiert
        zahlen[0] = 0;
        zahlen[1] = 0;

        // Fuegen Sie Ihre Implementierung hier ein.
        for (int i = 2; i <= n; i++){
            for (int j = 2; j < i; j++){
                if(i%j == 0){
                    zahlen[i] = 0;
                }
            }
        }
        
        int a = 0;
        for (int i = 0; i<= n; i++){
            if(zahlen[i] != 0){
                a++;
            }
        }
        
        int b = 0;
        int [] primzahlen = new int [a];
        

        for (int i = 0; i < a; i++){
            if (zahlen[i] != 0){
                primzahlen[b] = i;
            }
        }
        
        
        return zahlen;
    }
    
    public static void main(String[] args) {
        Prim prim = new Prim();
        
        int[] output = prim.primzahlenBestimmen(20);
        System.out.println("Die Primzahlen kleiner gleich 20 lauten:");
        // Mit der folgenden Zeile kann ein Feld testweise ausgegeben werden
        System.out.println(Arrays.toString(output));
    }
}

Mir werden hierbei aber neben den Primzahlen Nicht-Primzahlen angegeben, die mit Nullen markiert werden! In der Ausgabe sollen aber nur die Primzahlen ausgegeben werden.



Nun soll ich ja nur Primzahlen am Ende ausgeben und habe es dann mit diesem Ansatz probiert:

class Prim {
    int[] primzahlenBestimmen(int n) {
        int[] zahlen = new int[n+1];

        // Zunaechst sind alle Zahlen nicht markiert
        for (int i = 0; i <= n; i++) {
            zahlen[i] = i;
        }

        // 0 und 1 sind keine Primzahlen, werden daher markiert
        zahlen[0] = 0;
        zahlen[1] = 0;

        // Fuegen Sie Ihre Implementierung hier ein.
        for (int i = 2; i <= n; i++){
            for (int j = 2; j < i; j++){
                if(i%j == 0){
                    zahlen[i] = 0;
                }
            }
        }

        int a = 0;
        for (int i = 0; i<= n; i++){
            if(zahlen[i] != 0){
                a++;
            }
        }
        
        int b = 0;
        int anzahl = 0;
        int [] primzahlen = new int [a];

        for (int i = 0; i < a; i++){
            if (zahlen[i] != 0){
                zahlen[b] = i;
                primzahlen[anzahl] = i;
                anzahl++;
            }
        }
        
        
        return primzahlen;
    }
    
    public static void main(String[] args) {
        Prim prim = new Prim();
        
        int[] output = prim.primzahlenBestimmen(20);
        System.out.println("Die Primzahlen kleiner gleich 20 lauten:");
        // Mit der folgenden Zeile kann ein Feld testweise ausgegeben werden
        System.out.println(Arrays.toString(output));
    }
}

Alle Primzahlen unter 10 werden richtig angegeben, aber alle über werden als 0 ausgegeben. Wie mache ich das, dass diese auch noch korrekt angegeben werden? Ich habe auch bereits im Forum meines Kurses die Frage gestellt. Nur will ich eben mehrere Meinungen erhalten können.

Danke im Voraus für eure Hilfe!

 

[KonradN]

Dein Algorithmus ist schlicht falsch!

Kannst du den Algorithmus einmal beschreiben in Worten? Und dann so wie beschrieben durchspielen (so, wie es ja auch gefordert ist).

 

[KonradN]

Also um es auch ganz deutlich zu sagen: das aufschreiben und durchspielen bezieht sich sowohl auf das Sieb, das du implementieren sollst als auch auf das Kopieren der Werte.

Denn ersteres ist nicht das geforderte Sieb und zweites ist schlicht falsch.

 

[Jw456]

Bei deinem Sieb innere Schleife sollst du ja von der gerade aktiven Zahl bis zum Ende der Reihe gehen. Machst du schon mal nicht.
Dann Prüfen ob es ein vielfaches der Zahl ist wenn ja löschen in der Reihe.

Vor dem weiter schalten zur nächsten Zahl prüfen ob sie schon gelöscht ist.

Das Sieb des Eratosthenes - lernen mit Serlo!

Entdecke das Sieb des Eratosthenes: Ein Verfahren, um systematisch Primzahlen zu bestimmen. Finde heraus, wie du alle Primzahlen einer Liste herausfiltern kannst.

de.serlo.org

 

[Zentriks]

Habs jetzt gelöst. int b habe ich gar nicht gebraucht und anstatt i < a, muss es i < n heißen, bei meiner zweiten Schleife.

 

[KonradN]

Habs jetzt gelöst. int b habe ich gar nicht gebraucht und anstatt i < a, muss es i < n heißen, bei meiner zweiten Schleife.

Ok, du hast damit erst einmal das zweite Problem: "Kopieren der Werte" gelöst.

Das ändert aber nichts daran, dass Dein Algorithmus nicht das Sieb des Eratosthenes implementiert. Du gehst einfach durch und prüfst für jede Zahl, ob dies eine Primzahl ist und das ist schlicht nicht die Anforderung!

Daher: Schau Dir doch einfach einmal an, was denn der Algorithmus "Sieb des Eratosthenes" genau ist und implementiere diesen korrekt.