(Java) Happy Numbers in Anlehnung an den Sieb des Eratosthenes (Glueckliche Zahlen)

[Unfaehig]

Hey Leute,

ich benötige eure Hilfe bei folgender Aufgabenstellung: Programmiere eine Klasse, welche eine Zahl uebergeben bekommt und anhand dieser Zahl einen Array mit der Laenge der uebergebenen Zahl erstellt. Anschließend wird der geamste Array auf true gesetzt. Danach soll jedes 2.te Array auf false gesetzt werden, von den übrig gebliebenen Arrays (also die, die noch ture sind) soll jedes dritte Array auf false gesetzt werden usw. Zum Schluss soll ausgegeben werden welche Array noch auf true sind.

Beispiel:
1) 1,2,3,4,5,6,7,8,9,10
2) 1,*,3,*,5,*,7,*,9,*
3) 1,3,*,7,9
4) 1,3,7,*
5) Ausgabe: 1,3,7



Mein Loesungsansatz:

public class HappyNumbers {
  public static void happy ( boolean[] s) {
        int n = s.length;                                          //für die for-schleifen
        for (int k = 0; k < n; k++) {
            s[k] = true;                                          //alle Arrays werden erst einmal auf "true" gesetzt
        }
        
        
        for (int i = 1, k=2; i < n; i=i+k){              //Ausfilterung der Unhappy Numbers
        	      s[i]=false;
        
        	      if (i+k>=n){                            //der Index wird zurückgesetzt und die Schrittweite wird um 1 erhöht
          		i=0;
        		k++;
        	}
        	
        }
    	 
    }
    
    public static void main( String[] args) {
  
        int n = Integer.parseInt(args[0]);
        
      boolean[] tabelle = new boolean[n];// default-Init. = false
      
      System.out.println("Happy Numbers: ");
      happy(tabelle);
      for ( int i = 2; i < n; ++i) 
          if (tabelle[i] == true)
              System.out.print( i + " ");
   }
}

Bei diesem Lösungsansatz wird das Arrayfeld 6 schon auf false gesetzt - also die Dezimalzahl 7...wie könnte man das effektiv umgehen?
Ich hatte noch andere Ansätze wie:

 public static void happy ( boolean[] s) {
        int n = s.length;
        for (int k = 0; k < n; k++) {
            s[k] = true;
        }
        
        
        for (int i = 0, k=2; i < n; i=i+k){           //i wurde hier auf 0 gesetzt und man greift mit [i+1] auf die Array Speicherzellen zu
        			s[i+1]=false;
      	
               	if (i+k>=n){
        		i=0;
        		k++;
        	}
        	
        }

Bei dieser Lösung läuft er über den Array-Index hinaus...und mir fällt keine möglichkeit ein, wie ich das umgehen kann. Ich hatte mir gedacht, dass man das evtl mit einer Fallabfrage -dass nur dann auf false gesetzt wird, wenn bereits ein Wert vorhanden ist- lösen könnte.

for (int i = 0, k=2; i < n; i=i+k){
        	if(s[i+1]==true || s[i+1]==false){
        			s[i+1]=false;
        	}
      	
               	if (i+k>=n){
        		i=0;
        		k++;
        	}
        	
        }

Auch hierbei entsteht ein Überlauf, so dass das Programm beendet wird und ich keine Ahnung habe wie ich diesen Fehler umgehen könnte.

Hätte von euch evtl jemand einen Lösungsansatz, oder ist eine der Teillösungen schon ansatzweise richtig?

Ich habe das Gefühl, dass ich komplett auf dem Holzweg bin...

Vielen Dank im Voraus😀

 

[Lonsdaleit]

Was mir direkt auffällt ist, dass du immer das gesamte array durchläufst, also auch die Werte die false sind.

Wenn du also die Länge 10 hast, gehst du für k=2,k=3,k=4 etc immer die komplette Länge 10 durch.

Du musst die auf false gesetzten Elemente entweder löschen (aufpassen wegen Überlauf) oder die, die auf true sind in ein neues Array übertragen.

Ich empfehle dir eine rekursive Methode, der ein Array und k übergeben wird.
In dieser Methode gehst du das Array, wenn k < länge des Array, durch und setzt alle vielfachen von k auf false.
Dann erstellst du ein neues Array in der du nur die true-elemente übergibst.
Du zählst k um eins hoch und rufst die Methode selbst wieder mit k und dem neuen Array auf.

Das Array, das übrigbleibt (wenn k größer als länge des Array) ist dein Ergebnis-Array.
Da du die alten Arrays nicht mehr brauchst, kannst du auch ein globales Array erstellen für dein Ergebnis, dass du immer überschreibst.
Damit ersparst du es dir, das Array aus der rekursiven Methode heraus zuübergeben.

Gruß