Desbordamiento de pila al calcular el número primo 10,001 en Java

Question

Estoy haciendo el problema 7 del Proyecto Euler. Lo que se supone que debo hacer es calcular el número primo 10,001 ^st. (Un número primo es un número entero mayor que uno que sólo es divisible por sí mismo y uno.)

Aquí es mi programa actual:

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

Funciona bien con hallazgo, dicen que el 100 ^º primer número, pero funcionando con entradas muy grandes (como 10,001) da como resultado el desbordamiento de la pila. ¿Por qué y cómo puedo solucionar esto?

Answer 1

Creo que el problema es que está llamando recursivamente al Prime para determinar si un número es principal o no. Entonces, para determinar si el número 1000 es primo o no, estás llamando al Prime 1000 veces de manera recursiva. Cada llamada recursiva requiere que los datos se mantengan en la pila. La pila es solo muy grande, por lo que eventualmente te quedas sin espacio en la pila para seguir haciendo llamadas recursivas. Intente usar una solución iterativa en lugar de una solución recursiva.

Answer 2

Para resolver esto, en general, tendrá que pasar de una solución recursiva a una iterativa. (Todos los algoritmos recursivos se pueden expresar de forma iterativa, también).

Como la función Prime es recursiva, siempre habrá un límite del sistema para la cantidad de veces que puede llamarse a sí mismo.

Sin embargo, puede tener suficiente memoria en su sistema para alcanzar 10001. Java le permite establecer la cantidad máxima de memoria (pila, pila, etc.) que utiliza la máquina virtual. Aumenta el número de memoria de la pila, y probablemente puedas hacerlo. Ver esta página

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

para algunas de las opciones de Java VM.

Answer 3

Deberías guardar todos los números primos que tienes hasta ahora en una lista de búsqueda, por lo tanto, verificaras si el número está dividido por los números de esa lista. Si no es un número primo, ve a agregarlo a la lista.
Otra idea es reemplazar number++; con number += 2; y comenzar a verificar desde 3 tan pronto como los números pares con excepción de 2 no sean primos.

Answer 4

Recientemente resolví este problema. Sugeriría generar sus números primos con un Sieve of Eratosthenes, decir todos los primos < 1 millón. No es un algoritmo difícil de implementar, y es bastante rápido para la cantidad de primos que necesita.

Answer 5

Los compiladores para algunos idiomas (por ejemplo, muchos lenguajes funcionales y semifuncionales como Lisp) convertirán recursividad de cola como la que ha usado en la iteración, pero (aparentemente) el compilador de Java no lo hace por usted. Como resultado, cada llamada recursiva usa espacio de pila, y finalmente se agota y la pila se desborda.

Por supuesto, para la mayoría de los propósitos, desea utilizar un algoritmo diferente; lo que está utilizando en este momento es bastante horrible ya que estas cosas van. Por lo menos, solo necesita verificar los números impares hasta la raíz cuadrada del número que está probando ...

Answer 6

Su estrategia para probar un primo es verificar su divisibilidad con cada número natural más pequeño.

Si cambia su estrategia para probar la divisibilidad con cada primo más pequeño, ahorrará una gran cantidad de cálculos.

Answer 7

fuente de Uso "Sieve of Eratosthenes"

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

siempre se puede utilizar la prueba de primalidad Rabin-Miller. Es un algoritmo muy fácil de implementar y muy rápido, aunque entender cómo funciona es un poco más difícil.

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

esta es mi respuesta de trabajo.

Answer 11

El problema radica en la recursivamente función definida Prime(X,Y), pero también en el algoritmo utilizado. Solo hay demasiada recursión profundidad que el mecanismo de llamada a función de Java puede acomodarse antes de que se agote la pila de llamadas, causando el error de "desbordamiento de pila".

Es suficiente para probar la divisibilidad frente a todos los números por debajo de la raíz cuadrada del número que se está probando. En términos del código OP, eso significa comenzar no desde Prime(N,N-1), sino desde Prime(N, floor(sqrt(N+1))). Este cambio solo podría ser suficiente para evitar el error SO para esta tarea específica, ya que la profundidad de recursión cambiará de 10000 a solo 100.

Los problemas algorítmicos solo comienzan ahí. El código Prime(X,Y) cuenta abajo, por lo tanto, primero pruebe el número por números más grandes. Pero los factores más pequeños se encuentran mucho más a menudo; el conteo se debe hacer desde el factor más pequeño posible, 2 (que se encuentra para el 50% de los números), hasta al sqrt del número de candidato. La función debe volver a escribirse como un simple bucle while en esta oportunidad, también.

La siguiente mejora fácil y obvia es ignorar por completo los números pares. 2 es conocido por ser primo; todos los otros pares no son. Eso significa que a partir del bucle de numberOfPrimes = 1; number = 3; y contando por number += 2 para enumerar sólo los números impares, teniendo isPrime(N) prueba su divisibilidad sólo por las números impares, así, en un bucle while comenzando con X = 3, las pruebas de N % X y contando por X += 2.

O en pseudocódigo (en realidad, Haskell), el código original es

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 

la solución propuesta:

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 

Timings mostrados son para código no compilado en GHCi (en una computadora portátil lenta). Empirical local orders of growth tomado como log(t2/t1)/log(n2/n1). Aún más rápido es probar por números primos, y no por números impares.

por cierto, las impresiones de códigos originales no prime la centésima primera, pero el número por encima de ella.

Answer 12

En C ... Usted puede hacer versión más corta, pero lo que sea: 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); 
} 

}