Problema del setaccio di Eratostene: gestire numeri davvero grandi

Question

Sto risolvendo il giudice online di Sphere Generatore principale usando il setaccio di Eratostene.

Il mio codice funziona per il caso di prova fornito. Ma .. come afferma chiaramente il problema:

L'ingresso inizia con il numero T dei casi di test in una singola riga (t <= 10). In ciascuna delle righe T successive ci sono due numeri M e N (1 <= m <= n <= 1000000000, nm <= 100000) separato da uno spazio.

So che il metodo Integer.parseInt() lancia un'eccezione durante la gestione di numeri davvero grandi e il giudice online indicava che era stata lanciata un'eccezione, quindi ho cambiato ogni caso di parseInt a parseLong nel mio codice.

Bene, la cosa sta funzionando bene su NetBeans 6.5 con valori piccoli per m e 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("");
       }
}

}

Input+output:

run:
2
1 10
2
3
3
5
7

3 5
3
5

BUILD SUCCESSFUL (total time: 11 seconds)

Ma Jcreator Le sta dicendo questo:

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.

Qui non ho un overflow intero, ma perché Jcreator dovrebbe lamentarsi?

Considerando la Testcase borderline, il programma implode anche su NetBeans:

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

Come posso affrontare quegli enormi numeri interi della dichiarazione del problema?

Modificare: Per suggerimento ho cambiato l'array booleano per un bitset, ma sto ancora ottenendo un 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

Ecco il tuo problema:

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

Ciò utilizzerà un'enorme quantità di spazio poiché alloca 4 byte per booleano per consentire un accesso più rapido. Usare un java.lang.bitset per evitarlo.

Alla fine, i tuoi numeri potrebbero diventare troppo grandi anche per molto tempo e dovrai usare Biginteger. Ma a quel punto, il setaccio di Eratostene probabilmente non lo taglierà più.

Answer 2

Stai usando molto spazio per conservare i tuoi booleani. Potresti provare a spremere ogni booleano in un po '. E pensaci, hai davvero bisogno di un booleano per ogni numero tra la parte inferiore e in alto? I numeri pari ad esempio non sono mai primi (tranne 2), né tutti i multipli di 3 (tranne 3) ecc. Questa pagina Potrebbe darti delle buone idee.

Answer 3

C'era un piccolo bug nell'implementazione del bitset. La linea:

                    isComposite.set(m);

dovrebbe effettivamente essere:

                    isComposite.set(k);

Con quella riga fissata, il codice è stato eseguito senza errori nel caso di prova da 999900000 a 1000000000, sputando 4.832 numeri primi che iniziano con 999900017 e termina con 999999937. Il bitset ha usato 125 Mbyte di memoria e il metodo ha impiegato 17 secondi per correre sul mio 2,2 GHZ computer portatile.

Answer 4

Ae stai usando la classe Biginteger? Perché se no, lo consiglio vivamente qui. Affronterà i grandi numeri che stai descrivendo. Se ciò non è abbastanza buono, è necessario allocare più memoria da utilizzare per JVM facendo -xmx come parametro della riga di comando. C'è un esempio qui:

http://www.coderanch.com/t/384456/java-geneeral-intermediete/java/increase-jvm-heap-size-eclipse

C'è anche un grossodecimale, se hai bisogno di numeri decimali per essere grandi.

Answer 5

Avevo affrontato problemi simili a causa delle limitazioni sulla dimensione del heap di Java. Invece di usare un numero intero di memoria elevata, il passaggio a Booleano ha risolto il problema. Trova il codice allegato:

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