Erreur lors de la recherche de nombres premiers plus importants

Question

J'ai fait un simple programme de tamisage des erastothènes pour calculer la somme des nombres premiers jusqu'à n pour le projet euler. Il fonctionne très bien pour 100, 1 000, 10 000 et ainsi de suite, mais quand je fais 1 ou 2 millions d'euros, il me donne ceci:

java.lang.ArrayIndexOutOfBoundsException: -2146737495

Il ne se produit pas pour les petits nombres, j'utilise des tableaux booléens.

boolean[] primes = new boolean[2000001]; 
    ArrayList<Integer> list = new ArrayList<Integer>(); 
    for (int i = 2; i < primes.length; i++){ 
     primes[i] = true; 
    } 
    boolean stop = false; 
    int target = 2; 
    int cycles = 1; 
    while (!stop) { 
     list.add(target); 
     for (int i = target;; i ++) // 
     { 
      if (target*i >= primes.length) {// 
       break; 
      } 
      primes[target*i] = false;// 

     } 
     for (int i = target + 1; ; i ++) { 

      if(i >= primes.length) { 
       stop = true; 
       break; 
      } 
      else if (primes[i]) { 
       target = i; 
       break; 
      } 
     } 
     cycles ++; 
    } 
    int sum = 0; 
     for (int i = 0; i < list.size(); i++) { 
     sum += list.get(i);; 
    } 

Mon but est pas du tout vraiment trouver la réponse, mais plusieurs fois je l'ai abandonné mon code en raison de ces types d'erreurs. J'aimerais trouver une source pour eux.

Answer 1

C'est parce que vous utilisez un int, qui a une limite supérieure de 2^31-1: voir https://en.wikibooks.org/wiki/Java_Programming/Primitive_Types

Pour gérer de grands nombres, vous devez utiliser la classe BigInteger.

Answer 2

Vous avez un problème avec votre baie primes. Tout d'abord, en lisant l'erreur, votre tableau n'est clairement pas assez long pour votre logique puisque vous le définissez comme boolean[] primes = new boolean[2000001]; et vous avez une exception ArrayIndexOutOfBoundsException de -2146737495. Essayez donc d'utiliser un long ou un BigInteger au lieu d'un int pour les variables i, target et cycles. Même ainsi, vous devrez repenser votre logique puisque le problème n'est pas le débordement par lui-même, mais le tableau qui n'est pas assez long.

Answer 3

Une vérification incorrecte ne prend pas en compte le débordement d'entier.

for (int i = target;; i ++) // 
{ 
    if (target*i >= primes.length) {// This is the check 
     break; 
    } 
    primes[target*i] = false;// Here is where it overflows 

} 

Une fois que vous frappez un i qui fait target * i plus grand qu'un entier peut contenir, les trop-pleins entiers. Cela signifie que maintenant cela deviendra négatif. Et bien sûr, pour un nombre négatif, target*i >= primes.length sera faux.

Et bien sûr, un nombre négatif ne peut pas être un index dans un tableau. Il aurait dû s'arrêter à la pause, mais pas parce que la condition n'a pas été remplie.

Ce que vous devez faire est de calculer la i maximale autorisée, et de mettre ce que la condition de la boucle:

int maxI = primes.length/target; 
for (int i = target; i < maxI; i ++) // 
{ 
    primes[target*i] = false;// Here is where it overflows 
} 

Le maxI est le nombre maximum que vous pouvez multiplier par target et toujours pas atteindre le primes.length . Maintenant, vous n'avez plus besoin de votre chèque (car multiplier target par i ne donnera jamais un nombre supérieur à primes.length et il ne débordera jamais, car la multiplication donne toujours un nombre inférieur à la taille du tableau, donc moins . que Integer.MAX_VALUE

une autre méthode, moins coûteux (moins multiplications) serait:

if (primes.length/target >= target) { 
    for (int i = target * target; i < primes.length; i += target) // 
    { 
     primes[i] = false; 
    } 
} 

le contrôle du if est nécessaire pour éviter tout débordement dans le cas où vous avez un énorme target.