Overflow de pile lors du calcul du 10 001ème numéro principal en Java

Vous pouvez toujours utiliser le Test de primalité RABIN-MILLER . C'est un algorithme très facile à mettre en œuvre et très rapide, bien que la compréhension de la façon dont cela fonctionne est un peu plus difficile.

import java.util.*;

public class LargestPrime {
    public static boolean isPrime(long s) {
        for(long i = 2; i < s; i++) {
            if((s % i) == 0) return false;                   
        }
        return true;
    }

    public static void main(String[] args) {
        LargestPrime p = new LargestPrime();
        LinkedList<Long> arr = new LinkedList<Long>();
        for(long j = 2; j <= 999999; j++) {

            if(isPrime(j)) arr.add(j);

        }
        // System.out.println("List of Prime Number are: "+ arr);
        long t = arr.get(10001);

        System.out.println("The Prime Number At 10001st position: " + t);
    }
}

package problems;

public class P_7 {
    /**
     * @param args
     */
    public static boolean prime(double num)
    {
        double x=2;
        double limit=(int) ((num/2)-(num/2)%1);
        while(x<=limit)
        {
            if(num%x==0)
                return false;
            x++;
        }
        return true;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int i=1;
        int j=3;
        while(i<=10000)
        {
            if(prime(j))
            {
                System.out.println(i);
                i++;
                System.out.println(j);
            }
            j++;
        }
    }
}
this is my working answer.

Le problème réside dans le de la fonction défini em> défini (x, y) code> fonction, mais aussi dans l'algorithme utilisé. Il n'y a que beaucoup de récursion profondeur em> que le mécanisme d'appel de fonction de Java peut accueillir avant l'épuisement de la pile d'appel, provoquant l'erreur "Overflow de pile".

Il suffit de tester la divisibilité contre tout Nombres sous la racine carrée du nombre en cours de test. En termes de code OP, cela signifie de commencer non à partir de Prime (n, n-1) code>, mais plutôt de Prime (n, plancher (sqrt (n + 1))) code>. Ce changement pourrait être suffisant pour éviter l'erreur si une erreur pour cette tâche spécifique, car la profondeur de la récupération passera de 10000 à seulement 100. p>

Les problèmes algorithmiques commencent que là-bas. Le code prime (x, y) code> compte down em> strong>, teste donc le nombre de nombres plus gros en premier. Mais des facteurs plus petits sont trouvés beaucoup plus souvent; Le comptage doit être effectué à partir du plus petit facteur possible, 2 (qui est rencontré pour 50% de chiffres), up em> strud> au sqrt code> de la numéro de candidat. La fonction doit être réécrite comme un simple pendant code> en boucle à cette opportunité, aussi. P>

Prochaine amélioration facile et évidente consiste à ignorer les numéros pairs. 2 est connu pour être premier; Tous les autres Evens ne sont pas. Cela signifie démarrer la boucle de numérymofyprime = 1; Numéro = 3; code> et comptant par Number + = 2 code> pour énumérer des nombres impairs uniquement, avoir isprime (n) code> Testez leur divisibilité uniquement par le Numéros impairs em> également, dans un pendant code> en démarrant avec x = 3 code>, test pour n% x code> et comptant par x + = 2 code>. p>

ou dans pseudocode em> (réellement, haskell), le code d'origine est p> xxx pré>

Le correctif proposé: p>

main = print ((2:[n | n<-[3,5..], isOddPrime(n)]) !! 10000)  where   
  isOddPrime(n) = _Prime(3)  where
         _Prime(y) = (y*y) > n || (rem n y > 0 && _Prime(y+2)) 
  -- 100:0.02s 200:0.03s 300:0.04s 5000:3.02s 10000:8.60s
  --                                       n^1.5

en C ... Vous pouvez faire une version plus courte, mais quoi que ce soit: d .. xxx