Problema de tamiz de Eratosthenes: manejo de números realmente grandes

Question

Estoy resolviendo el juez en línea de la esfera Generador principal Usando el tamiz de Eratóstenes.

Mi código funciona para el caso de prueba proporcionado. Pero ... como dice claramente el problema:

La entrada comienza con el número T de casos de prueba en una sola línea (t <= 10). En cada una de las siguientes líneas T hay dos números M y N (1 <= m <= n <= 1000000000, nm <= 100000) separado por un espacio.

Sé que el método Integer.parseInt() lanza una excepción al manejar números realmente grandes y el juez en línea indicaba que se estaba lanzando una excepción, por lo que cambié todos los casos de parseInt a parseLong en mi código.

Bueno, la cosa está funcionando bien en NetBeans 6.5 con pequeños valores para M y 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("");
       }
}

}

Entrada+salida:

run:
2
1 10
2
3
3
5
7

3 5
3
5

BUILD SUCCESSFUL (total time: 11 seconds)

Pero JCreator le dice esto:

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.

Aquí no tengo un desbordamiento entero, pero ¿por qué JCreator se quejaría?

Teniendo en cuenta la prueba de prueba límite, el programa también se implosiona en 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

¿Cómo puedo lidiar con esos enormes enteros de la declaración del problema?

Editar: Por sugerencia, he cambiado la matriz booleana para un bitset, pero todavía estoy obteniendo 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("");
       }
}

}

De entrada y salida:

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

Aquí está tu problema:

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

Esto utilizará una gran cantidad de espacio, ya que asigna 4 bytes por boolean para permitir un acceso más rápido. Utilizar una java.lang.bitset para evitar eso.

Eventualmente, sus números pueden ser demasiado grandes para mucho tiempo y tendrá que usar Biginteger. Pero en ese momento, el tamiz de Eratóstenes probablemente ya no lo cortará.

Answer 2

Estás usando mucho espacio para almacenar tus booleanos. Puede intentar exprimir cada booleano en un bit. Y piénselo, ¿realmente necesitas un booleano para cada número entre el borde inferior y el borde superior? Los números par, por ejemplo, nunca son primos (excepto 2), ni todos son múltiplos de 3 (excepto 3), etc. Esta página podría darte algunas buenas ideas.

Answer 3

Hubo un pequeño error en la implementación de su bitset. La línea:

                    isComposite.set(m);

en realidad debería ser:

                    isComposite.set(k);

Con esa línea solucionada, el código funcionó sin errores en el caso de prueba 9999900000 a 1000000000, escupiendo 4,832 primos a partir de 9999900017 y terminando con 999999937. El bitset usó 125 mbytes de memoria, y el método tomó 17 segundos para correr en mi 2.2 GHz computadora portátil.

Answer 4

¿Estás usando la clase Biginteger? Porque si no, lo recomiendo aquí aquí. Se ocupará de los grandes números que está describiendo. Si eso no es lo suficientemente bueno, entonces debe asignar más memoria para que el JVM lo use haciendo -xmx como parámetro de línea de comandos. Hay un ejemplo aquí:

http://www.coderanch.com/t/384456/java-general-intermediate/java/increase-jvm-teap-size-eclipse

También hay un BigDecimal, si necesita números decimales para ser grandes también.

Answer 5

Me había enfrentado problemas similares debido a las limitaciones en el tamaño del montón de Java. En lugar de usar un entero de memoria alta, cambiar a boolean resolvió el problema. Encuentra el código adjunto:

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