Dépassement de la pile lors du calcul du nombre premier 10,001st en Java

StackOverflow https://stackoverflow.com/questions/2485620

  •  21-09-2019
  •  | 
  •  

Question

Je suis en train de faire problème 7 du projet Euler. Ce que je suis censé faire est de calculer le 10001 er nombre premier. (Un nombre premier est un nombre entier supérieur à celui qui est seulement divisible par lui-même et une.)

Voici mon programme en cours: 

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 nombre premier, mais en cours d'exécution avec des entrées très importantes (comme 10001) se traduit par un débordement de pile. Pourquoi, et comment puis-je résoudre ce problème?

Était-ce utile?

La solution

Je pense que le problème est que vous récursive appeler 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écursive. Chaque appel récursif nécessite des données à garder sur la pile. La pile est seulement si grand, si finalement vous manquez de place sur la pile de continuer à faire des appels récursifs. Essayez d'utiliser une solution itérative au lieu d'une solution récursive.

Autres conseils

Utilisez " d'Eratosthène Sieve"

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

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

J'ai récemment résolu ce problème. Je vous suggère de générer vos nombres premiers avec un Sieve d'Eratosthène , disent tous les nombres premiers <1 million. Ce n'est pas un algorithme difficile à mettre en œuvre, et il est assez rapide pour le nombre de nombres premiers dont vous avez besoin.

Compilateurs pour certaines langues (par exemple plusieurs langages fonctionnels et semi-fonctionnels comme Lisp) convertiront récursion queue comme vous avez utilisé dans l'itération, mais (apparemment) le compilateur Java ne fait pas pour vous. En conséquence, chaque appel récursif utilise l'espace de pile, et éventuellement de vous lancer et les débordements de pile.

Bien sûr, pour la plupart des cas, vous souhaitez utiliser un algorithme différent - ce que vous utilisez est assez en ce moment terrible que ces choses vont. À tout le moins, il vous suffit de vérifier les numéros impairs jusqu'à la racine carrée du nombre que vous testez ...

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

Si vous passez votre stratégie pour tester la divisibilité avec juste chaque petit premier, vous économiseriez beaucoup de calcul. 

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

Pour résoudre ce en général, vous allez devoir passer d'une solution récursive pour un processus itératif. (Chaque algorithme récursif peut être exprimé de manière itérative, aussi.)

Depuis que le premier est la fonction récursive, il y aura toujours une limite du système combien de fois il peut appeler lui-même.

Cependant, vous pouvez avoir assez de mémoire sur votre système pour atteindre 10001. Java vous permet de définir que la machine virtuelle utilise la quantité maximale de mémoire (pile, tas, etc.). Augmenter le nombre de mémoire de la pile, et vous serez probablement en mesure de le faire. Voir cette page

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

pour certaines des options Java VM. 

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

est ma réponse de travail.

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

Le problème réside dans la récursive défini la fonction Prime(X,Y), mais aussi dans l'algorithme utilisé. Il y a seulement tellement récursivité profondeur que le mécanisme d'appel de fonction de Java peut accueillir avant que la pile d'appel est épuisé, ce qui provoque l'erreur « débordement de pile ».

Il suffit de tester la divisibilité contre tous les chiffres de la racine carrée du nombre testé. En ce qui concerne le code OP, cela signifie pas de départ Prime(N,N-1), mais plutôt de Prime( N, floor( sqrt( N+1)) ). Ce seul changement pourrait être suffisant pour éviter l'erreur SO pour cette tâche spécifique, comme la profondeur de récursivité passera de 10 000 à seulement 100

problèmes algorithmiques commencent seulement là. Les chiffres de code Prime(X,Y) bas , testant ainsi le nombre par le nombre plus grand d'abord. Mais les petits facteurs se trouvent beaucoup plus souvent; le comptage doit être fait du plus petit facteur possible, 2 (que l'on rencontre pour 50% des nombres), up à la sqrt du nombre de candidats. La fonction doit être réécrite comme une simple boucle de while à cette occasion, aussi.

Amélioration suivante facile et évidente est d'ignorer les nombres pairs tout à fait. 2 est connue pour être prime; tous les autres ne sont pas Evens. 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 impair numéros ainsi, dans une boucle de while commençant par X = 3, les tests pour N % X et comptant 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

minutages sont présentés pour code non compilé dans GHCi (sur un ordinateur portable lent). commandes locales de croissance empirique prises en log(t2/t1) / log(n2/n1). Encore plus rapide teste par les nombres premiers, et non par des nombres impairs.

BTW, les impressions de code d'origine et non le premier 10001e, mais le chiffre au-dessus.

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

}

Non affilié à StackOverflow
scroll top