Sieb von Eratosthenes Problem: wirklich große Zahlen behandeln

Question

Ich löse Sphere's Online Richter Prime Generator mit dem Sieb von Eratosthenes.

Mein Code funktioniert für den bereitgestellten Testfall. Aber .. wie das Problem eindeutig fest:

Die Eingabe beginnt mit der Nummer t von Testfällen in einer einzigen Zeile (t < = 10). In jedem der nächsten t Linien gibt es zwei Zahlen m und n (< 1 = m = n < < = 1000000000, n-m < = 100000) durch einen Raum getrennt.

Ich weiß, dass das Verfahren Integer.parseInt() eine Ausnahme auslöst, wenn wirklich große Zahlen Umgang mit und die Online-Richter wurde darauf hinweist, dass eine Ausnahme ausgelöst wurde, also habe ich jeden Fall von parseInt-parseLong in meinem Code.

Nun, die Sache läuft gut auf Netbeans 6.5 mit kleinen Werten für m und n.

package sphere; 

import java.io.BufferedReader; 
import java.io.InputStreamReader; 

public class Main{ 

public static void runEratosthenesSieve(long lowerBound, long upperBound) { 

     long upperBoundSquareRoot = (long) Math.sqrt(upperBound); 

     boolean[] isComposite = new boolean[(int)upperBound + 1]; 

     for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) { 

      if (!isComposite[m]) { 

       if (m>=lowerBound) {System.out.println(m);} 

        for (int k = m * m; k <= upperBound; k += m) 

         isComposite[k] = true; 

      } 

     } 

     for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++) 

      if (!isComposite[m]) 

       if (m>=lowerBound){ System.out.println(m);} 

} 

public static void main(String args[]) throws java.lang.Exception{ 

     BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); 


     String l = r.readLine(); 

     int testCases = Integer.parseInt(l); 

     for (int i =0; i<testCases; i++){ 
     String s =r.readLine(); 

     String []splitted=s.split(" "); 


     long lowerBound = Long.parseLong (splitted[0]); 
     long upperBound = Long.parseLong(splitted[1]); 

     runEratosthenesSieve (lowerBound,upperBound); 

     System.out.println(""); 
     } 
} 

} 

Eingang + Ausgang:

run: 
2 
1 10 
2 
3 
3 
5 
7 

3 5 
3 
5 

BUILD SUCCESSFUL (total time: 11 seconds) 

Aber JCreator LE dies sagt:

2 
1 10 
Exception in thread "main" java.lang.NumberFormatException: For input string: "" 
    at java.lang.NumberFormatException.forInputString(NumberFormatException.java:48) 
    at java.lang.Long.parseLong(Long.java:424) 
    at java.lang.Long.parseLong(Long.java:461) 
    at sphere.Main.main(Main.java:51) 

Process completed. 

Hier habe ich keine Integer-Überlauf, aber warum sollte JCreator beschweren?

In Anbetracht der Borderline-Testfall, implodiert das Programm auf Netbeans zu:

run: 
2 
999900000 1000000000 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
     at sphere.Main.runEratosthenesSieve(Main.java:13) 
     at sphere.Main.main(Main.java:55) 
Java Result: 1 

Wie kann ich mit diesen riesigen ish ganzen Zahlen der Problemstellung umgehen?

Edit: Mit dem Vorschlag, den ich habe den boolean-Array für eine BitSet geändert, aber ich bin noch immer ein OutOFMemoryError:

package sphere; 

import java.io.BufferedReader; 
import java.io.InputStreamReader; 
import java.util.BitSet; 

public class Main{ 

public static void runEratosthenesSieve(long lowerBound, long upperBound) { 

     long upperBoundSquareRoot = (long) Math.sqrt(upperBound); 

     //boolean[] isComposite = new boolean[(int)upperBound + 1]; 

     BitSet isComposite = new BitSet((int)upperBound+1); 

     for (int m = 2 /*int m = lowerBound*/; m <= upperBoundSquareRoot; m++) { 

      if (!isComposite.get(m)) { 

       if (m>=lowerBound) {System.out.println(m);} 

        for (int k = m * m; k <= upperBound; k += m) 

         isComposite.set(m); 

      } 

     } 

     for (int m = (int)upperBoundSquareRoot; m <= upperBound; m++) 

      if (!isComposite.get(m)) 

       if (m>=lowerBound){ System.out.println(m);} 

} 

public static void main(String args[]) throws java.lang.Exception{ 

     BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); 


     String l = r.readLine(); 

     int testCases = Integer.parseInt(l); 

     for (int i =0; i<testCases; i++){ 
     String s =r.readLine(); 

     String []splitted=s.split(" "); 


     long lowerBound = Long.parseLong (splitted[0]); 
     long upperBound = Long.parseLong(splitted[1]); 

     runEratosthenesSieve (lowerBound,upperBound); 

     System.out.println(""); 
     } 
} 

} 

Input-Output:

run: 
1 
999900000 1000000000 
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
     at java.util.BitSet.initWords(BitSet.java:144) 
     at java.util.BitSet.<init>(BitSet.java:139) 
     at sphere.Main.runEratosthenesSieve(Main.java:16) 
     at sphere.Main.main(Main.java:58) 
Java Result: 1 
BUILD SUCCESSFUL (total time: 14 seconds) 

Answer 1

Hier ist Ihr Problem:

boolean[] isComposite = new boolean[(int)upperBound + 1]; 

Dies wird eine große Menge an Speicherplatz verwenden, da es 4 Byte pro boolean ordnet, um einen schnelleren Zugriff zu ermöglichen. Verwenden Sie eine java.lang.BitSet, um dies zu vermeiden.

Schließlich werden Ihre Nummern möglicherweise auch zu lange zu groß und Sie müssen BigInteger verwenden. Aber an diesem Punkt wird das Sieb von Eratosthenes wahrscheinlich auch nicht mehr schneiden.

Answer 2

Ae Sie mit die BigInteger-Klasse? Denn wenn nicht, empfehle ich es hier. Es wird sich mit den großen Zahlen beschäftigen, die Sie beschreiben. Wenn das nicht gut genug ist, müssen Sie der JVM mehr Speicher zuweisen, indem Sie -Xmx als Befehlszeilenparameter verwenden. Es gibt hier ein Beispiel:

http://www.coderanch.com/t/384456/Java-General-intermediate/java/Increase-JVM-heap-size-eclipse

Es gibt eine BigDecimal ist auch, wenn Sie Dezimalzahlen müssen auch groß sein.

Answer 3

Sie verwenden viel Platz, um Ihre Booleschen Werte zu speichern. Sie könnten versuchen, jeden booleschen Wert in ein Bit zu quetschen. Und denken Sie darüber nach, brauchen Sie wirklich einen booleschen Wert für jede Nummer zwischen unterer und oberer Grenze? Die geraden Zahlen sind zum Beispiel niemals Primzahlen (außer 2), noch sind alle Vielfachen von 3 (außer 3) usw. This page könnte Ihnen einige gute Ideen geben.

Answer 4

Es gab einen kleinen Fehler in Ihrer BitSet-Implementierung. Die Linie:

    isComposite.set(m); 

eigentlich sein sollte:

    isComposite.set(k); 

Mit dieser Linie festgelegt, wird der Code lief ohne Fehler auf dem Testfall 999.900.000-1000000000, spuckt 4832 Primzahlen mit 999.900.017 beginnen und enden mit 999.999.937 Das BitSet verwendete 125 Mbytes Speicher, und die Methode dauerte 17 Sekunden, um auf meinem 2,2 GHz Laptop zu laufen.

Answer 5

Ich hatte ähnliche Probleme aufgrund der Einschränkungen auf Java Heap Size. Anstelle der Verwendung von Integer mit hohem Speicher löste das Verschieben auf Boolean das Problem. Finden den beigefügten Code:

public ArrayList<Integer> sieve(int A) { 
    boolean prime [] = new boolean[A + 1]; 
    Arrays.fill(prime, true); 
    prime[0] = prime[1] = false; 

    for (int i = 2; i <= A; i++) { 
     if (!prime[i]) 
      continue; 

     for (long j = 1L * i * i; j <= (long) A; j += i) 
      prime[(int) j] = false; 
    } 

    ArrayList<Integer> res = new ArrayList<>(); 

    for (int i = 0; i <= A; i++) { 
     if (prime[i]) 
      res.add(i); 
    } 

    return res; 
}