Factor primo más grande de un número muy largo

[DickGumshoe]

Hola.

Para entretenerme, estoy haciendo problemas en C de una página de Internet que son como retos.  

Uno de ellos dice así:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Sería algo como: "Los factores primos de 13195 son 5, 7, 13 y 29. ¿Cuál es el factor primo más grande de 600851475143 ?"

He intentado esto:

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>

int main()
{
   long long int i, resultado;
   long long int MAX = 600851475143;
   int num;

   for( i = 2; i < MAX; i++)
   {
      if(MAX % i == 0)
      {
          MAX /= i;
          i = 2;
       }
   }

   printf("El maximo factor primo de 600851475143 es %d\n\n", MAX );

   system("pause");
   return 0;
}



Pero no me da el resultado correcto  

He hecho varios intentos, pero nada...

Saludos.

[ralymontes]

Te funcion primo no calcula si es o no primo... Checa en el foro, hay un tema reciente sobre numeros primos, incluso codigo que podria ayudarte.

Saludos.

[do-while]

¡Buenas!

A parte de la logica de tu codigo (solo intentas mostrar numeros primos menores que un valor dado, pero no compruebas que sean factores de dicho numero), el problema esta en que estas tratando con elementos mayores que un entero de 4 bytes. Si no puedes manejar enteros de mas de 4 bytes, es posible que tengas que recurrir a reglas de divisibilidad (que no siempre son evidentes)... En este momento no se me ocurre nada mas, aunque seguro que hay algo... (pero no lo veo XD)

¡Saludos!

[DickGumshoe]

Muchas gracias a los dos por responder.

En este código se me olvidó comprobar que los números primos obtenidos sean factores del número dado, pero ha sido al ponerlo en el foro, antes lo tenía pero lo borraría haciendo pruebas, supongo. Ahora lo hago de nuevo y edito el primer mensaje.

Sí, uno de los problemas que he tenido ha sido que al ser un número tan grande, por mucho que pusiera long long int, a veces el ordenador se inventa un número... Intentaré ver qué puedo hacer respecto a esto.

¿Entonces la función esPrimo no calcula bien si un número es primo o no? He hecho varias pruebas y creo que sí lo hace bien, al menos con números bajos...

Saludos.

[DickGumshoe]

Le he hecho algunas modificaciones al programa.

Me he dado cuenta que no necesito hallar si un número es primo o no, ya que si empiezo a ver los divisores del "número grande" desde el 2 hacia delante, siempre será divisible antes por un número primo que por uno compuesto. Así me calcula todo mucho más rápido, ¡y llega a la solución correcta! 

Saludos.

[do-while]

¡Buenas!

Tu solucion ne parece elegante, ahora lo explico. Te falte algun detalle, dividir mientras se pueda por el divisor dado y acumular el divisor en otra variable. Si tenemos la descomposicion en factores primos del numero, p1^n1*...*pk^nk, suponiendo que los pi esten ordenados de menor a mayor, mientras vas recorriendo el bucle de divisores encontraras el primer divisor posible, p1. Y tendras que hacer:

guadar el divisor en la variable auxiliar.

[en este paso eliminas p1^n1 como factor del numero]
mientras puedas dividir el numero por p1

    numero = numero / p1;

fin mientras

Esto lo haras con cada uno de los divisores que encuentres (Solo pueden ser primos por lo que ya he mencionado). En cuanto llegues al ultimo divisor, numero saldra con valor 1 del bucle, i > numero, saldra del bucle for y tendras acumulado en la variable auxiliar el ultimo (y mayor) divisor primo del numero. No se si sera el mejor metodo para calcular el mayor divisor primo, pero con unas pocas modificaciones puedes obtener la descomposicion en factores primos del numero dado.

Código (c) [Seleccionar] Expandir


for(i = 2 ; i < numero ; i++)
{
    if(numero % i == 0)
    {
        aux = i;

        while(numero % i == 0)
            numero /= i;
    }
}

//aux saldra del for con el valor del mayor divisor primo.

¡Saludos!


[DickGumshoe]

Muchas gracias, do-while.

Tu solución es mucho más eficiente que la mía.

Saludos.

[do-while]

¡Buenas!

Espera, que el algoritmo no cuadra siempre. Voy a ver como lo arreglo.

¡Saludos!

Ya lo tengo. La cosa esta en darse cuenta de que el valor de salida que tendra numero depende del exponente del mayor factor primo que tenga.

Si nk == 1, significa que al eliminar p_k-1 como factor, el valor que tomara numero es pk. Como i va avanzando de uno en uno, y buscamos valores menores que numero, nunca alcanzara el valor pk, y nunca dividiremos numero por pk, por lo que el valor de salida de numero sera pk.

Si nk > 1, al eliminar p_k-1 como factor, el valor de numero sera pk^nk, con nk >= 2. Por lo que tendremos pk < pk^nk, e i si que alcanzara el valor pk, por lo que al eliminar pk como divisor de numero, numero saldra con valor 1.

Por lo tanto el divisor que buscamos sera:

Si numero != 1 -> numero
sino i - 1;

[DickGumshoe]

Muchas gracias, no me había dado cuenta de eso 

Saludos.

[do-while]

¡Buenas!

Si que ando espeso estos dias... (el calor y los examenes...). Por lo que he comentado en el ultimo post, basta poner i <= numero (como condicion de fin de for), y asi siempre se tendra que i - 1 es el mayor de los divisores primos.

¡Saludos!