Erste Schritte Primzahlen-ArrayIndexOutOfBounds

[Nikolai98]

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

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]);
//        }
}
}

 

[httpdigest]

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:

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));
}

 

[Xyz1]

@httpdigest es kann noch optimiert werden?

@Nikolai98 meinst Du den Algorithmus Sieb des Eratosthenes (sehr effizient) ? Dann darf N aber glaub ich nicht fest sein.

 

[httpdigest]

@httpdigest es kann noch optimiert werden?

Na aber sicher doch

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);
}

 

[Xyz1]

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

 

[Xyz1]

Nebenbeiangemerkt,
https://www.quora.com/How-many-prime-numbers-are-there-between-1-and-1000

hier wird auch das Boole Sylvester principle genannt (das ich aber nirgends finde).

 

[mihe7]

Ne ich meinte einfach Deinen Algo aus Beitrag #2

Man könnte ausnutzen, dass Primzahlen > 2 ungerade sind...

 

[httpdigest]

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:

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)];

 

[mihe7]

Sag mal, wie kommst Du auf solche Ideen?!?

 

[httpdigest]

Frag @Tobias-nrw , ist ja bestimmt seine Idee.

 

[mihe7]

Anders gefragt: beschäftigst Du Dich intensiver mit Primzahlen oder googlest Du das Zeug bei Bedarf?

 

[httpdigest]

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.

 

[Xyz1]

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.

 

[mihe7]

Ist das genau? Gilt es für alle x? (Vermutlich nicht).

Was heißt genau? Es ist eine obere Schranke in Abhängigkeit von x für π(x). Die Abschätzung ist für alle x >= 2 gültig.

 

[mihe7]

hier wird auch das Boole Sylvester principle genannt (das ich aber nirgends finde).

Verschiedene Autoren scheinen das https://en.wikipedia.org/wiki/Inclusion–exclusion_principle so zu nennen.

 

[Xyz1]

@mihe7 wie viele Primzahlen liegen im geschlossenen Intervall von 9'999'999'999'999'999 bis 19'999'999'999'999'999 ?

 

[Xyz1]

Wolfram Alpha gibt dazu keine Antwort:

 

[mihe7]

@mihe7 wie viele Primzahlen liegen im geschlossenen Intervall von 9'999'999'999'999'999 bis 19'999'999'999'999'999 ?

Ca. 268420385630264; die Antwort lautet aber 42. Bin ich Jesus?

EDIT: korrekterweise müsste es lauten: höchstens 268420385630264

 

[Xyz1]

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)

 

[httpdigest]

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.

 

[mihe7]

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?

 

[Xyz1]

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!

 

[mihe7]

da diese immer noch ungenau sein könnte.

Irgendwie schreiben wir aneinander vorbei. Wenn der TE genau N Primzahlen will, dann stellt sich die Frage nach einer oberen Schranke nicht.

 

[Xyz1]

Irgendwie schreiben wir aneinander vorbei.

Ich sachs ja, das liegt am neuen Style des Forums.

... So Thema zuende, fertigdiskutiert.