Erste Schritte Primzahlen-ArrayIndexOutOfBounds

Nikolai98

Neues Mitglied
Hey,

ich bin relativ neu in Java und habe Schwierigkeiten bei einer Aufgabe die ich lösen möchte.

Und zwar würde ich gerne einen Array mit Primzahlen füllen. Dies funktioniert auch, allerdings werden die Stellen des Arrays, welche keine Primzahlen sind mit 0 gefüllt. Da ich nicht wusste wie man das behebt, habe ich nun einfach versucht einen zweiten Array zu erstellen und diesen nur mit den Stellen aus dem ersten Array zu füllen welche nicht gleich 0 sind. Hierbei springt mein Array allerdings immer out of Bounds und ich weiß nicht warum.

Ich würde mich über eure Hilfe freuen, gerne auch Vorschläge wie man das ganze eleganter lösen kann 😉

Java:
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int berreich = scanner.nextInt();
       
      //  Scanner jedeXte = new Scanner(System.in);
      //  int jedeXte2 = scanner.nextInt();

        int[] primzahl = new int[berreich];
        int primzahlRealLänge = 0;
        boolean istPrimzahl;
       
       
        for (int i = 2; i <berreich; i++) {
           
            istPrimzahl = true;
           
            for (int j = 2; j < i; j++) {
               
                if ((i % j) == 0) {
                    istPrimzahl = false;
                    break;
                }
            }
           
            if (istPrimzahl) {
                primzahl[i] = i;
                //System.out.println(primzahl[i]);
               
            }
        }
       
       
        for (int i = 0; i < berreich; i ++) {

            System.out.println(primzahl[i]);
        }
       
       
       
        for (int i = 0; i<berreich; i ++) {
            if (primzahl[i] != 0 ) {
                primzahlRealLänge = primzahlRealLänge + 1;
            }
        }
       
        System.out.println(primzahlRealLänge);
       
        int [] primzahlReal = new int [primzahlRealLänge];
       
        for (int i = 0; i < berreich; i++) {
            if (primzahl[i] != 0) {
                primzahl[i] = primzahlReal[i];
            }
        }
       
       
       
//        for (int i = 0; i < primzahlRealLänge; i ++) {
//  
//            System.out.println(primzahlReal[i]);
//        }
}
}
 
Der Fehler ist erstmal kein Compiler-Fehler, sondern ein Laufzeitfehler (das Problem tritt erst zur Laufzeit auf).
Desweiteren liegt die Ursache darin, dass du den gesamten Bereich von 1..N in der letzten Schleife durchläufst, aber das Array `primzahlReal` nicht so groß ist.
Mögliche Lösung: Erstmal ein Array aufmachen, bei dem nicht der Index `i` für die Zahl `i` steht, sondern für die `i`-te Primzahl. Und dann am Schluss noch das Array "stutzen", je nachdem, wieviele Primzahlen tatsächlich gefunden und in das Array geschrieben wurden:
Java:
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);
  int N = scanner.nextInt();
  int[] kandidaten = new int[N];
  int num = 0;
  for (int i = 1; i <= N; i++) {
    boolean prim = true;
    for (int j = 2; prim && j <= Math.sqrt(i); j++)
      prim &= i % j != 0;
    if (prim)
      kandidaten[num++] = i;
  }
  int[] primzahlen = Arrays.copyOf(kandidaten, num);
  System.out.println(Arrays.toString(primzahlen));
}
 
@httpdigest es kann noch optimiert werden?
Na aber sicher doch 🙂
Java:
public static void main(String[] args) {
  int N = new java.util.Scanner(System.in).nextInt();
  java.util.BitSet sieb = new java.util.BitSet(N);
  java.util.stream.IntStream
   // alle Zahlen von 2 bis (einschließlich) N
   .rangeClosed(2, N)
   // nur noch nicht ausgesiebte Zahlen
   .filter(i -> !sieb.get(i))
   // siebe Vielfaches von dieser Zahl 'i' aus
   .peek(i -> java.util.stream.IntStream
             .iterate(i, j -> j <= N, j -> j + i)
             .forEach(sieb::set))
   // Hau alle Primzahlen raus!
   .forEach(System.out::println);
}
 
So meinte ich das nicht, Du hast jetzt DSDE funktional umgesetzt. 😉
BitSet Einsparungen sind auch fragwürdig.

Ne ich meinte einfach Deinen Algo aus Beitrag #2
 
Vielleicht meint er auch, dass man den Upper-Bound der π-Funktion abschätzen kann, um das Ergebnisarray π(N) statt N Einträge groß zu alloziieren:
Java:
private static int π(int x) {
  // https://arxiv.org/pdf/1706.09803.pdf
  if (x < 60184)
    return (int) Math.ceil(x / Math.log(x) * (1 + 3 / (2 * Math.log(x))));
  return (int) Math.ceil(x / (Math.log(x) - 1.1));
}
...
public static void main(String[] args) {
  ...
  int[] kandidaten = new int[π(N)];
 
Okay, in diesem Fall war es nur eine reine Frage aus Neugierde, wieviele Primzahlen bis N es eigentlich gibt. Surely hat da irgendjemand schon irgendeine Formel für. Und so kommt man vom einen zum nächsten.
 
Frag @Tobias-nrw , ist ja bestimmt seine Idee. 😀
Habe ich das irgendwo angedeutet?

Ne ich meinte die zuhilfenahme
dass Primzahlen > 2 ungerade sind
verringert dann (insofern nicht funktional programmiert) die Laufzeit um zusätzliche 50 %.

Vielleicht meint er auch, dass man den Upper-Bound der π-Funktion abschätzen kann
Ist das genau? Gilt es für alle x? (Vermutlich nicht). 🙁

Also Beitrag #2 könnte eine akzeptable Lösung "andeuten", insofern Du die nicht funktional geschrieben hättest. 🙄 Außerdem habe ich nirgendwo geschrieben ich sei der Primzahlen-Guru ...

@Nikolai98 , Brauchst Du N Primzahlen
ODER alle Primzahlen bis N? Das stellt hier einen gewichtigen Unterschied dar. 🙄
 
EDIT: korrekterweise müsste es lauten: höchstens 268420385630264 🙂
Und da ist ja das Problem, keine genaue Angabe machen zu können. 🙄

Der Intervallabschnitt ist zu hoch und zu groß. Und natürlich, etwas schwammig, gäbe es eine genaue Formel dafür, so würde Wolfram Alpha diese angeben.

Es kann aber auch sein das ich mich wieder etwas aus dem Fenster gelehnt habe... und es bei WA iewann angegeben werden wird. 🙄

Wir können uns jetzt noch über die Begriffe genau sowie zu hoch und zu groß streiten. 😀 (Sieht man davon ab, dass sich diese aus dem Kontext ergeben könnten) 🙁
 
Es ging doch niemals darum, genau zu sein. Die Abschätzung ist aber immer noch sehr viel besser als keine Abschätzung, bzw. als einfach N zu verwenden.
 
Und da ist ja das Problem, keine genaue Angabe machen zu können.
Das ist kein Problem, da es hier um Komplexität geht.

Nehmen wir mal die binäre Suche in einer sortierten Liste. Dort hast Du eine Laufzeitkomplexität von O(log n). Du wirst zustimmen, dass diese Suche einer linearen Suche mit einer Komplexität von O(n) vorzuziehen ist. Du kannst aber nicht genau sagen, nach wie vielen Schritten Du den Herrn Müller gefunden hast. Das spielt letztlich keine Rolle: die Schrittzahlfunktion der binären Suche wächst nicht wesentlich schneller als log n und die der linearen Suche nicht wesentlich schneller als n.

Genau das gleiche haben wir hier auch - nur eben nicht (direkt) auf Laufzeit sondern auf Platz bezogen. Nimmst Du ein Array mit n Elementen, hast Du eine Platzkomplexität von O(n) (bzw. Θ(n)). Nimmst Du ein Array mit n/log n Elementen eben von O(n/log n).

Vereinfacht: ist es besser 10^16 oder 2,69*10^14 Elemente reservieren zu müssen?
 
Also jetzt mal realistisch... 🙄

In diesem Zahlenbereich ( https://de.wikipedia.org/wiki/Zahlennamen#Billion,_Billiarde_und_darüber_hinaus -> 9 Billiarden bis 19 Billiarden (ja das musste ich nachgucken (ja du hast beim Zitat meine Zahlen verdreht 🙄 ))), in diesem Zahlenbereich nützt eine obere Platzabschätzung (also z. B. new int[N + 1000] oder new int[N + 10000]) (praktisch) NIX mehr, da diese immer noch ungenau sein könnte.

Es kommt einfach auf die Frage des TE an... Möchte ich/er/sie/es genau N Primzahlen oder mindestens / höchstens N Primzahlen ermitteln... Das ist mir noch nicht so genau klar. 😉 (Sorry wegen des Wortspiels 😵 )

Dennoch Danke ich euch beiden für die ganzen, fachlichen Erläuterungen zu dieser Sache. (die ich noch nicht kannte)🙂

Bearbeitung(!!!) ODER in etwa N Primzahlen!
 
Zuletzt bearbeitet von einem Moderator:

Neue Themen


Zurück
Oben