Problème de tamis d'eratosthène: gérer de très gros chiffres

Question

Je résolve le juge en ligne de Sphere Générateur de premier plan Utilisation du tamis des eratosthènes.

Mon code fonctionne pour le cas de test fourni. Mais .. Comme le problème l'indique clairement:

L'entrée commence par le nombre t de cas de test en une seule ligne (t <= 10). Dans chacune des lignes t suivantes, il y a deux nombres m et n (1 <= m <= n <= 1000000000, nm <= 100000) séparé par un espace.

Je sais que la méthode Integer.parseInt() Jette une exception lors de la gestion de très gros chiffres et le juge en ligne indiquait qu'une exception était lancée, alors j'ai changé tous les cas de parseInt à parseLong dans mon code.

Eh bien, la chose est bien fonctionnelle sur NetBeans 6.5 avec de petites valeurs pour m et 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("");
       }
}

}

Entrée + sortie:

run:
2
1 10
2
3
3
5
7

3 5
3
5

BUILD SUCCESSFUL (total time: 11 seconds)

Mais Jcreator Le dit ceci:

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.

Ici, je n'ai pas de débordement entier, mais pourquoi JCreator se plaindrait-il?

Compte tenu du testcase limite, le programme implose également sur 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

Comment puis-je gérer ces entiers énormes de l'énoncé du problème?

Éditer: Par suggestion, j'ai changé le tableau booléen pour un ensemble de bits, mais je reçois toujours 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("");
       }
}

}

Entrée sortie:

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

Voici votre problème:

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

Cela utilisera une énorme quantité d'espace car il alloue 4 octets par booléen afin de permettre un accès plus rapide. Utiliser un java.lang.bitset pour éviter cela.

Finalement, vos chiffres pourraient également devenir trop importants et vous devrez utiliser BigInteger. Mais à ce moment-là, le tamis des eratosthènes ne le coupera probablement plus.

Answer 2

Vous utilisez beaucoup d'espace pour stocker vos booléens. Vous pourriez essayer de serrer chaque booléen dans un bit. Et pensez-y, avez-vous vraiment besoin d'un booléen pour chaque nombre entre le benbound et le haut en haut? Les nombres pair, par exemple, ne sont jamais privilégiés (sauf pour 2), ni tous les multiples de 3 (sauf pour 3) etc. Cette page pourrait vous donner de bonnes idées.

Answer 3

Il y avait un petit bug dans votre implémentation BitSet. La ligne:

                    isComposite.set(m);

devrait être en fait:

                    isComposite.set(k);

Avec cette ligne fixe, le code s'est déroulé sans erreurs sur le cas de test 999900000 à 1000000000, crachant 4 832 nombres premiers commençant par 999900017 et se terminant par 999999937. L'ETT a utilisé 125 mbytes de mémoire, et la méthode a pris 17 secondes pour fonctionner sur mon 2,2 ghz 2,2 ghz portable.

Answer 4

Vous utilisez la classe BigInteger? Parce que si non, je le recommande vivement ici. Il traitera des grands nombres que vous décrivez. Si ce n'est pas assez bon, vous devez allouer plus de mémoire pour que le JVM puisse utiliser en faisant -xmx comme paramètre de ligne de commande. Il y a un exemple ici:

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

Il y a aussi un BigDecimal, si vous avez également besoin que les chiffres décimaux soient grands.

Answer 5

J'avais fait face à des problèmes similaires en raison des limites de la taille du tas de Java. Au lieu d'utiliser un entier de mémoire élevé, le passage à Boolean a résolu le problème. Trouvez le code ci-joint:

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