1

No entiendo donde esta el error, pero aca hay un ciclo infinito. Me es muy complicado hacer la traza dado que es recursividad cruzada. Quizas ustedes que son mas expertos en estos temas me puedan ayudar en esto. Soy un estudiante de Ingenieria en Computacion. Saludos.

Ps: El codigo esta en java.

public class Primo{
     //Averigua si un numero es primo de una manera recursiva
    public boolean esPrimo (int n){
        return esPrimoRecursivo(n,2);
    }

    private boolean esPrimoRecursivo (int n, int divisor){ //ESTA MAL
        boolean resul;
        if (n == 2)
            resul = true; //N ES PRIMO
        else if (n > 2){
                if (divisor == n)
                    resul = true; //N ES PRIMO
                else
                    if (n % divisor == 0)
                        resul = false; //N NO ES PRIMO
            }
        resul = esPrimoRecursivo(n,siguienteNumeroPrimo(n));
        return resul;
    }

    private int siguienteNumeroPrimo (int k){
        if (esPrimoRecursivo(k+1,2))
            return k+1;
        return siguienteNumeroPrimo (k+1);
    }
}
0

1 respuesta 1

2

Tu problema está en resul = esPrimoRecursivo(n,siguienteNumeroPrimo(n)); cuando haces eso sobreescribes lo que tenía resul y repites el proceso infinitamente. Cuando se da la condición de parada debes retornar inmediatamente.

Modificando ese detalle y quitando el método siguienteNumeroPrimo porque no lo necesitas, el código quedaría así:

class Primo{
    //Averigua si un numero es primo de una manera recursiva        
    public boolean esPrimo (int n){
        return (n >= 2) && esPrimoRecursivo(n,2);
    }

    private boolean esPrimoRecursivo (int n, int divisor){
        if (n == 2)
            return true; //N ES PRIMO
        else if (n > 2){
            if (divisor == n)
                return true; //N ES PRIMO
            else
            if (n % divisor == 0)
                return false; //N NO ES PRIMO
        }

        return esPrimoRecursivo(n,divisor+1);
    }
}

Aquí te dejo una versión un poco más optimizada porque si lo piensas bien en realidad no hace falta dividir contra todos los números que anteceden al que estás buscando:

class Primo{
    public boolean esPrimo (int n){
        return (n >= 2) && tail_esPrimo(n, (int) (Math.sqrt(n) + 1));
    }

    public boolean tail_esPrimo(int numero, int divisor) {
        if(divisor <= 1)
            return true;

        if(numero % divisor == 0)
            return false;

        return tail_esPrimo(numero, divisor - 1);
    }
}
1
  • Bien perfecto, gracias, evidentemente probar con todos los numeros primos era super ineficiente e innecesario. Me sirvio perfectamente tu solucion saludos :)
    – Ravenant
    Commented el 21 may. 2020 a las 18:15

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.