Débordement de pile lors du calcul du 10 001ème nombre premier en Java

Question

Je fais le problème 7 du projet Euler. Ce que je suis supposé faire est de calculer le nombre premier de 10 001 ^st. (Un nombre premier est un entier supérieur à celui qui est divisible par lui-même et un.)

Voici mon programme actuel:

public class Problem7 { 
    public static void main(String args[]) { 
     long numberOfPrimes = 0; 
     long number = 2; 

     while (numberOfPrimes < 10001) { 
      if (isPrime(number)) { 
       numberOfPrimes++; 
      } 
      number++; 
     } 
     System.out.println("10001st prime: " + number); 
    } 

    public static boolean isPrime(long N) { 
     if (N <= 1) 
      return false; 
     else 
      return Prime(N, N - 1); 
    } 

    public static boolean Prime(long X, long Y) { 
     if (Y == 1) 
      return true; 
     else if (X % Y == 0) 
      return false; 
     else 
      return Prime(X, Y - 1); 
    } 
} 

Il fonctionne bien avec la conclusion, disons 100 ^e premier nombre, mais en cours d'exécution avec de très grandes entrées (telles que 10 001) entraîne un débordement de pile. Pourquoi, et comment puis-je résoudre ce problème?

Answer 1

Je pense que le problème est que vous appelez récursivement Prime pour déterminer si un nombre est premier ou non. Donc, pour déterminer si le nombre 1000 est premier ou non, vous appelez Prime 1000 fois récursivement. Chaque appel récursif nécessite que les données soient conservées dans la pile. La pile est seulement si grande, donc vous finirez par manquer de place sur la pile pour continuer à faire des appels récursifs. Essayez d'utiliser une solution itérative au lieu d'une solution récursive.

Answer 2

Pour résoudre ceci en général, vous allez devoir passer d'une solution récursive à une solution itérative. (Chaque algorithme récursif peut aussi être exprimé itérativement.)

Puisque la fonction Prime est récursive, il y aura toujours une limite système sur le nombre de fois qu'elle peut s'appeler elle-même. Cependant, vous pouvez avoir suffisamment de mémoire sur votre système pour atteindre 10001. Java vous permet de définir la quantité maximale de mémoire (pile, tas, etc.) que la VM utilise. Augmentez le nombre de mémoire de la pile, et vous serez probablement capable de le faire. Voir cette page

http://docs.sun.com/source/817-2180-10/pt_chap5.html

pour certaines des options Java VM.

Answer 3

Vous devriez enregistrer tous les nombres premiers que vous avez obtenus jusqu'à présent dans une liste de recherche, par conséquent vous vérifierez si le nombre est divisé par les nombres de cette liste. Sinon, c'est un nombre premier - allez l'ajouter à la liste.
Une autre idée est de remplacer number++; par number += 2; et de commencer à vérifier à partir de 3 dès que les nombres pairs avec l'exception pour 2 ne sont pas premiers.

Answer 4

J'ai récemment résolu ce problème. Je suggère de générer vos nombres premiers avec un Sieve of Eratosthenes, dire tous les nombres premiers < 1 million. Ce n'est pas un algorithme difficile à implémenter, et c'est assez rapide pour le nombre de nombres premiers dont vous avez besoin.

Answer 5

Les compilateurs pour certaines langues (par exemple, de nombreux langages fonctionnels et semi-fonctionnels comme Lisp) convertissent la récursion de queue comme vous l'avez utilisée en itération, mais (apparemment) le compilateur Java ne le fait pas pour vous. Par conséquent, chaque appel récursif utilise l'espace de pile, et vous finissez par vous épuiser et la pile déborde.

Bien sûr, dans la plupart des cas, vous voulez utiliser un algorithme différent - ce que vous utilisez en ce moment est plutôt horrible. À tout le moins, vous devez seulement vérifier les nombres impairs jusqu'à la racine carrée du nombre que vous testez ...

Answer 6

Votre stratégie pour tester un nombre premier est de vérifier sa divisibilité avec chaque plus petit nombre naturel.

Si vous changez de stratégie pour tester la divisibilité avec chaque premier petit, vous économiserez beaucoup de calculs.

Answer 7

Utilisez "Sieve of Eratosthenes"

source de Java:

public class Main { 
    public static void main(String args []){ 
     long numberOfPrimes = 0; 
     int number = 1; 
     int maxLimit = 10000000; 
     boolean[] sieve = new boolean[maxLimit]; 
     for (int i = 2; i < maxLimit; i++) { 
      if (sieve[i] == true) continue; 

      numberOfPrimes++; 

      if (numberOfPrimes == 10001) { 
       number = i; 
       break; 
      } 

      for (int j = i+i; j < maxLimit; j += i) 
       sieve[j] = true; 
     } 
     System.out.println("10001st prime: "+ number); 
    } 
} 

Answer 8

Vous pouvez toujours utiliser le test de primalité Rabin-Miller. C'est un algorithme très facile à implémenter et très rapide, mais comprendre comment cela fonctionne est un peu plus compliqué.

Answer 9

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

Answer 10

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

ceci est ma réponse de travail.

Answer 11

Le problème réside dans la récursivement fonction définie Prime(X,Y), mais aussi dans l'algorithme utilisé. Il y a seulement autant de récursivité profondeur que le mécanisme d'appel de fonction de Java peut accueillir avant l'épuisement de la pile d'appels, provoquant l'erreur "stack overflow".

Il suffit de tester la divisibilité pour tous les nombres inférieurs à la racine carrée du nombre testé. Pour ce qui est du code OP, cela signifie qu'il ne faut pas commencer par Prime(N,N-1), mais plutôt par Prime(N, floor(sqrt(N+1))). Cette seule modification pourrait suffire à éviter l'erreur SO pour cette tâche spécifique, car la profondeur de récursivité passera de 10000 à 100 seulement.

Les problèmes algorithmiques commencent seulement là. Le code Prime(X,Y) compte vers le bas, testant ainsi le nombre en premier. Mais de plus petits facteurs sont trouvés beaucoup plus souvent; le comptage doit être effectué à partir du plus petit facteur possible, 2 (qui est rencontré pour 50% des nombres), jusqu'à du numéro de candidat. La fonction devrait être réécrite comme une simple boucle while à cette occasion, aussi.

Ensuite, une amélioration facile et évidente consiste à ignorer complètement les nombres pairs. 2 est connu pour être premier; tous les autres evens ne le sont pas. Cela signifie à partir de la boucle de numberOfPrimes = 1; number = 3; et de comptage par number += 2 d'énumérer les nombres impairs seulement, ayant isPrime(N) tester leur divisibilité que par les impairs numéros et, dans une boucle while commençant par X = 3, les tests pour N % X et le comptage par X += 2.

Ou dans pseudocode (en fait, Haskell), le code d'origine est

main = print ([n | n<-[2..], isPrime(n)] !! 10000) where 
    isPrime(n) = _Prime(n-1) where 
     _Prime(y) = y==1 || (rem n y > 0 && _Prime(y-1)) 
    -- 100:0.50s 200:2.57s 300:6.80s 10000:(projected:8.5h) 
    --  n^2.4  n^2.4 

le correctif proposé:

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 

détails ci sont pour le code non compilé dans GHCi (sur un ordinateur portable lent). Empirical local orders of growth pris comme log(t2/t1)/log(n2/n1). Encore plus rapide est le test par les nombres premiers, et non par des nombres impairs.

BTW, les impressions de code d'origine pas de prime 10001e, mais le chiffre au-dessus.

Answer 12

En C ... Vous pouvez faire la version plus courte, mais peu importe: D ..

#include <stdio.h> 
#include <stdlib.h> 

prost_br(int p) 
{ 
    int br=0; 

    for(int i=2;i*i<=p;i++) 
    if(p%i==0) 
    br++; 

    if(br==0) 
    return 1; 
    return 0; 
} 

int main() 
{ 
    long i=1; 
    int br=0; 
FILE *a; 

a=fopen("10001_prst_numbers.txt","w"); 
if(a==NULL){printf("\nError!\a\n"); exit(1);} 

    while(br!=10001) 
    { 
     i++; 
     if(prost_br(i)) 
     { 
      br++; 
      fprintf(a,"%d ",i); 
     } 

    } 
    char s[]={"10001th prime number is: "}; 
fprintf(a,"\n%s %d",s,i); 
fprintf(stdout,"\n10001th prime number is: %d\n\a",i); 

fclose(a); 
system("Pause"); 
} 

Answer 13

progs public class {

public int nthPrime(int nth) { 
    int ctr = 0; 
    int num = 0; 
    int x = 2; 
    int infinite = 15;   // initial value good for 6 prime values 
    while(x < infinite) { 
     boolean isPrime = true; 
     for(int i = 2; i <= x/2; i++) { 
      if(x % i == 0) { 
       isPrime = false; 
      } 
     } 
     if(isPrime) { 
      System.out.println(x); // optional 
      ctr++; 
      if(ctr == nth) { 
       num = x; 
       break; 
      } 
     } 
     x++; 
     if(x == infinite) {  // for bigger nth requested prime value 
      infinite++;  
     } 
    } 
    return num; 
} 

public static void main(String[] args) { 
    int ans = new progs().nthPrime(10001); 
    System.out.println("nth prime number is " + ans); 
} 

}