Sieb des Erathostenes

[worsel]

Ich habe die Aufgabe, alle Primzahlen von 1 bis zu einem von mir festgelegten Wert n herausschreiben zu lassen. Bekannt ist diese Aufgabe unter dem Namen 'Sieb des Erathostenes'.

Ich habe den Code soweit fertig, er funktioniert wunderbar, allerdings nur bis zu einem bestimmten Wert n, der ungefähr bei dem Wert 46.500 liegt.

Wenn ich das Programm dann starte, kommt folgende Fehlermeldung:

at siebdeserathostenes.Main.main(37871
Main.java:2937879

'Main.java:29' ist übrigens klickbar und führt mich zu Zeile 30.


Hier der Code:

package siebdeserathostenes;


public class Main {


    public static void main(String[] args) {
    
    
    int n = 46500;
    
    int[] prime = new int[n];
    boolean[] canceled;
    canceled = new boolean[n+1];
    
    long t1= System.nanoTime();
    
    for(int i=2; i<=n; i++){
        canceled[i] = false;
    }
    
    for(int i=2; i<=n; i++){
        if(canceled[i]== false){
            System.out.println(i);
            
            
            for(int j=i*i; j <= n; j=j+i){
                canceled[j]=true;
            }
        }
        
    }
            
    long t2 = System.nanoTime();
    long dauer = t2-t1;
    
    
    System.out.println();
    System.out.println("Dauer in Nanosekunden: "+dauer);
    System.out.println("Dauer in Sekunden: "+(double)dauer/1000000000);
    
    }
}

Die Fehlermeldung bringt bei jedem Programmstart verschiedene Zahlen raus, die alle etwa im gleichen Bereich liegen (~39000-41000), die verlinkte Programmzeile dazu bleibt jedes mal gleich.

Hat jemand eine Ahnung, warum dieser Fehler auftritt?
Das Programm läuft bis zu oben genanntem n einwandfrei...komisch


Grüße

 

[SlaterB]

public class Test {
    public static void main(String[] args) {
        int n = 46000;
        System.out.println(n * n);
        System.out.println(Integer.MAX_VALUE);
    }
}

 

[BJ]

Bei mir bei 46000:


2116000000
2147483647

Dann bei 46500:

-2132717296
2147483647


Fazit: Bereichsüberschreitung

So gehts dann natürlich:

public class Test2 {
    public static void main(String[] args) {
        int n = 46500;
        System.out.println((long)n * n); //Typecast eines Operanden
        System.out.println(Long.MAX_VALUE);
    }
}

2162250000
9223372036854775807

 

[worsel]

Vielen vielen Dank für eure schnellen Lösungsvorschläge, die absolut korrekt sind.
Dennoch habe ich einen Rat von einem Freund bekommen, folgende, falsche, Zeile zu verändern:

for(int j=i*i; j <= n; j=j+i){
                canceled[j]=true;
            }

Er meinte, ich solle als Startwert für j nur i nehmen, also j = i.
Damit sieht das so aus:

for(int j=i; j <= n; j=j+i){
                canceled[j]=true;
            }

Der Fehler liegt also offensichtlich nicht am Integerwert selbst, sondern an falscher Programmierung, was das Problem an sich angeht. Schande über mich

Wer den kompletten Code anschauen will, hier:

public class Main{


    public static void main(String[] args) {
        
        
    int n = 1000000;
    
    boolean[] canceled;
    canceled = new boolean[n+1];
    
    long t1= System.nanoTime();
    
    for(int i=2; i<=n; i++){
        canceled[i] = false;
    }
    
    for(int i=2; i<= n; i++){
        if(canceled[i]== false){
            System.out.println((long)i);
            
            
            for(int j=i; j <= n; j=j+i){
                canceled[j]=true;
            }
        }
        
    }
            
    long t2 = System.nanoTime();
    long dauer = t2-t1;
    
    
    System.out.println();
    System.out.println("Dauer in Nanosekunden: "+dauer);
    System.out.println("Dauer in Sekunden: "+(double)dauer/1000000000);
    
    }
}

 

[BJ]

Das meinte SlaterB auch mit "n*n"!

 

[SlaterB]

dass n*n gar nicht nötig ist, habe ich ehrlich gesagt nicht so genau gesehen,
in der Richtung ist aber natürlich immer etwas anzunehmen