entre Desarrolladores

Recibe ayuda de expertos

Registrate y pregunta

Es gratis y fácil

Recibe respuestas

Respuestas, votos y comentarios

Vota y selecciona respuestas

Recibe puntos, vota y da la solución

Pregunta

2votos

Bucle demasiado largo en C++? (No es un bucle infinito)

Hola, he escrito un código que debería devolverme el mayor factor primo de un número, pero el programa nunca llega a salir del bucle. El caso es que creo que el número que necesito introducir es demasiado largo y el programa se cuelga, pero si pruebo con un numero más pequeño el programa funciona sin problema.

#include <iostream>
using namespace std;

int long long factorPrimoMayor (int long long numero);

int main () {
    int long long numero = 600851475143;

    cout << factorPrimoMayor (numero);

    return 0;
}

int long long factorPrimoMayor (int long long numero) {
    int long long mayor;
    int long long i = numero-1;
    bool encontrado = false;

    while (!encontrado && (i > 1)) {
        if ((i%2 != 0) && (i%3 != 0)) {
            if (numero%i == 0) {
                mayor = i; // Como va de mayor a menor y solo me interesa el factor primo mas grande, solo necesito el primero que encuentre.
                encontrado = true;
            }
            else
                i--;
        }
        else
            i--;
    }

    return mayor;
}

2 Respuestas

1voto

Leonardo-Tadei Puntos227320

Hola @Yorji,

me puse a revisar tu código y tenés un problema de concepto en la implementación de buscar el mayor primo divisor.

Tu código orginal implementa bien la búsqueda, pero estás ignorando que sean divisores primos 2 y 3, por lo tanto, si el número llegase a tener estos valores como menor primo, nunca obtendrías un resultado.

Tu segundo código tampoco devuelve el resultado correcto, ya que estás devolviendo el primero que encontrás que no sea, 2, 3 o divisor de 2 o de 3, con lo que para valores chicos, nunca encontrás nada.

Tal vez yo esté entendiendo mal la consigna: para el número 74, el mayor divisor primo es 37, porque el 37 es primo y 37 * 2 = 74.

Si la consigna es esta, ninguno de tus dos algoritmos devuelven 37 cuando el valor ingresado es 74...

0voto

Yorji comentado

He compilado el código con 74 y si me devuelve 37. El bucle divide el número inicial entre el sus factores primos, de los más pequeños al más grande, el cual devuelve y sale del nucleo:

 if (numero == 1) // Es decir, es el último factor primo del número (y más grande)
       encontrado = true;

Si el factor primo es 2 o 3 también lo acepta:

if (((i%2 != 0) && (i%3 != 0)) || (i == 2) || (i == 3))

if: es primo (no se puede dividir entre 2 ni entre 3) o es 2 o 3.

0voto

Leonardo-Tadei comentado

Ya lo veo... tenía un error de sintaxis en mi código de prueba de tu 2do código.

Me desconcierta un poco el tratamiento particular que hacés de los valores 2 y 3... podrías ser tratados como cualquier otro número (a excepción del 1 que sí es un caso especial respecto a los números primos) y todo tiene que funcionar igual.

Si es por optimización, en vez de solo 2 valores, yo cargaría en el IF por ejemplo los primeros 10 o 20 primos.

Saludos!

0voto

Yorji comentado

No puedo tratar el 2 y el 3 como los demás números porque la forma que uso para averiguar si un número es primo es que no puede ser divido ni entro 2 ni entre 3.
2 es divisible entre 2 y 3 entre 3, por lo que daría que no son primos.

0voto

Leonardo-Tadei comentado

A eso me refería con que tratás a 2 y 3 como una excepción.

Un número es primo si solo es divisible por si mismo y por la unidad: tu algoritmo revisa que por ejemplo 7 no sea divisible por 6 ni 5 ni 4, pero tratás a 2 y 3 aparte.

Podrías tener un IF menos y verificar que 7 no sea divisible por 6 ni 5 ni 4 ni 3 ni 2 y así para cualquier número, sin tratar a 2 o 3 como casos particulares.

Es por esto que pensaba que era por una cuestión de eficiencia, para considerar primero 2 y 3 y luego entrar al bucle que verifica los demás valores... pero si fuera por eficiencia, sería mejor tratar aparte los primeros 10 o 20 primos. Si no hiciste esto por eficiencia, simplemente tenés un algoritmo que es más complicado de lo que debiera.

Igual, si funciona, no hay por qué tocarlo ;-)

0voto

Yorji comentado

Vale, he metido la pata...
Olvida el código anterior, esta mal planteado (aunque daba bien el resultado para ese preciso valor). He hecho esta funcion:

bool esPrimo (int long long numero) {
    bool ok = true;

    for (int i = 2; i < numero; i++)
        if (numero%i == 0)
            ok = false;

    return ok;
}

Lo que había hecho anteriormente no era correcto. He usado esta función para sustituir:

if (((i%2 != 0) && (i%3 != 0)) || (i == 2) || (i == 3))

Ahora de hecho parece que se ejecuta más rápido. Gracias por las respuestas, si sabéis alguna forma de mejorar el código soy todo oídos.

0voto

Leonardo-Tadei comentado

Hola @Yorji,

esta sí es una correcta implementación de un algoritmo que busque primos.

Podrías optimizarla de la siguiente manera: basta con encontrar 1 divisor para saber que no es primo y salir:

bool esPrimo (int long long numero) {
    for (int i = 2; i < numero; i++)
        if (numero%i == 0)
            return false;

    return true;
}

Así, por ejemplo al llamar a la función con valor 2000, sale en la primer iteracion y te ahorrás 1999 bucles.

Saludos cordiales!

PD: Para no confundir a los demás usuarios, marcá mi respuesta como "seleccionada" o publicá tu nuevo algoritmos como una respuesta aparte y marcala.

1voto

Yorji Puntos340

Me respondo a mi mismo. Sigo sin saber porque se queda pillado en ese bucle, pero de cualquier forma ese código esta mal. Este es el bueno:

#include <iostream>
using namespace std;

int long long factorPrimoMayor (int long long numero);

int main () {
    int long long numero = 600851475143;

    cout << factorPrimoMayor (numero);

    return 0;
}

int long long factorPrimoMayor (int long long numero) {
    int long long i = 2;
    bool encontrado = false;

    while (!encontrado) {
        if (((i%2 != 0) && (i%3 != 0)) || (i == 2) || (i == 3)) {
            if (numero%i == 0) {
                numero = numero/i;
                if (numero == 1)
                    encontrado = true;
                else
                    i = 2;
            }
            else
                i++;
        }
        else
            i++;
    }

    return i;
}

0voto

Peter comentado

Gracias por compartir la respuesta :)

0voto

Leonardo-Tadei comentado

Esta es la solución o es el código correcto de la pregunta???

0voto

Peter comentado

Buen punto Leonardo, yo solo leí el "me respondo a mi mismo", la vi en verde y di por hecho que era la respuesta :)
@Yorji ¿Si es la solución?

0voto

Yorji comentado

Es el código que estaba buscando (aunque sigo sin saber porque el otro código se cuelga).

0voto

Peter comentado

Ok, si este código soluciona el problema y hace lo mismo que estas preguntando, bien :)

Por favor, accede o regístrate para responder a esta pregunta.

Otras Preguntas y Respuestas


...

Bienvenido a entre Desarrolladores, donde puedes realizar preguntas y recibir respuestas de otros miembros de la comunidad.

Conecta