Desbordamiento de pila en el cálculo del número primo 10,001st en Java
https://stackoverflow.com/questions/2485620
-
21-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy haciendo problema 7 del Proyecto de Euler. ¿Qué se supone que tengo que hacer es calcular el 10,001 er número primo. (Un número primo es un número entero mayor que uno que sólo es divisible por sí mismo y uno.)
Aquí está 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 º número primo, pero corriendo con grandes entradas (por ejemplo, 10.001) da lugar a desbordamiento de pila. ¿Por qué y cómo puedo solucionar este problema?
Solución
Creo que el problema es que usted está llamando de forma recursiva Prime para determinar si un número es primo o no. Por lo tanto, para determinar si el número 1000 es primo o no, que está llamando Prime 1000 veces de forma recursiva. Cada llamada recursiva requiere datos a ser guardados en la pila. La pila es solamente tan grande, por lo que finalmente se queda sin espacio en la pila para seguir haciendo llamadas recursivas. Trate de usar una solución iterativa en lugar de una solución recursiva.
Otros consejos
Utilice " criba de Eratóstenes "
fuente 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);
}
}
Debe guardar todos los números primos que tengo hasta ahora en una lista mirada hacia arriba, por lo tanto se le mirando si el número se divide por el número de esa lista. Si no es un número primo - ir agregarlo a la Lista de amigos.
Otra idea es reemplazar number++; con number += 2; y empezar a comprobar a partir 3 tan pronto como los números incluso con excepción de 2 no son primos.
He resuelto este problema recientemente. Yo te sugeriría que la generación de sus primos con una criba de Eratóstenes , dicen que todos los primos <1 millón. No es un algoritmo difícil de poner en práctica, y es bastante rápido para el número de primos que necesita.
Los compiladores para algunos idiomas (por ejemplo, muchos lenguajes funcionales y semi-funcionales como Lisp) convertirá la recursión de cola como se ha utilizado en la iteración, pero (aparentemente) el compilador de Java no está haciendo eso para usted. Como resultado, cada llamada recursiva está utilizando espacio de pila, y, finalmente, salir corriendo a los desbordamientos de pila.
Por supuesto, para la mayoría de los propósitos, que desea usar un algoritmo diferente - lo que usted está usando en este momento está bastante mal ya que estas cosas pasan. Por lo menos, sólo es necesario para comprobar los números impares hasta la raíz cuadrada del número que está probando ...
Su estrategia para poner a prueba un número primo es comprobar su divisibilidad con cada número natural más pequeño.
Si usted cambia su estrategia para la prueba de divisibilidad con sólo cada primo más pequeño, que podría ahorrar una gran cantidad de cálculo.
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);
}
}
Para resolver este, en general, vas a tener que cambiar de una solución recursiva a un proceso iterativo. (Cada algoritmo recursivo se puede expresar de forma iterativa, también.)
Dado que la función Prime es recursivo, siempre habrá un límite de sistema para el número de veces que puede llamarse a sí misma.
Sin embargo, es posible que tenga memoria suficiente en el sistema para llegar a 10001. Java le permite establecer la cantidad máxima de memoria (pila, montón, etc.) que la máquina virtual utiliza. Aumentar el número de memoria de pila, y es probable que sea capaz de hacerlo. Ver esta página
http://docs.sun.com/source/817 -2,180-10 / pt_chap5.html
para algunas de las opciones de Java VM.
Siempre se puede utilizar el Rabin-Miller test de primalidad. Es muy fácil de implementar algoritmos y muy rápido, aunque la comprensión de cómo funciona es un poco más difícil.
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.
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");
}
El problema radica en el recursiva Prime(X,Y) función definida, sino también en el algoritmo utilizado. Sólo hay tanto recursividad profundidad que el mecanismo de llamada a la función de Java puede acomodar antes de que se agote la pila de llamadas, que causa el error "desbordamiento de pila".
Es suficiente para probar la divisibilidad en contra de todos los números debajo de la raíz cuadrada del número que se está probando. En términos del código OP, que no significa partir de Prime(N,N-1), sino más bien de Prime( N, floor( sqrt( N+1)) ). Este cambio por sí sola podría ser suficiente para evitar el error de SO para esta tarea específica, como el nivel de recursividad pasará de 10.000 a apenas 100.
problemas algorítmicos solamente comienzan allí. Los recuentos de código Prime(X,Y) por , probando así el número de números más grandes en primer lugar. Pero los factores más pequeños se encuentran mucho más a menudo; el recuento debe hacerse desde el factor más pequeño posible, 2 (que se encuentra el 50% de los números), a a la sqrt del número de candidatos. La función debe ser reescrita como un simple bucle while en esta oportunidad, también.
A continuación la mejora fácil y obvia es hacer caso omiso de los números pares en total. 2 se sabe que es primo; todos los demás iguala no lo son. Eso significa que a partir del bucle de numberOfPrimes = 1; number = 3; y contando por number += 2 enumerar solamente los números impares, teniendo isPrime(N) probar su divisibilidad sólo por el extraña números, 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
el arreglo propuesto:
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 un ordenador portátil lento). órdenes locales empíricos de crecimiento toman como log(t2/t1) / log(n2/n1). Aún más rápido está probando por números primos, y no por los números impares.
por cierto, las impresiones de código original no el primer 10001a, pero el número por encima de ella.
progs clase pública {
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);
}
}
