Question

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

Answer 1

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...

Answer 2

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