elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Factor primo más grande de un número muy largo
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Factor primo más grande de un número muy largo  (Leído 8,622 veces)
DickGumshoe


Desconectado Desconectado

Mensajes: 480



Ver Perfil WWW
Factor primo más grande de un número muy largo
« en: 4 Julio 2012, 01:24 am »

Hola.

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

Uno de ellos dice así:

Citar
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
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. int main()
  5. {
  6.    long long int i, resultado;
  7.    long long int MAX = 600851475143;
  8.    int num;
  9.  
  10.    for( i = 2; i < MAX; i++)
  11.    {
  12.       if(MAX % i == 0)
  13.       {
  14.           MAX /= i;
  15.           i = 2;
  16.        }
  17.    }
  18.  
  19.    printf("El maximo factor primo de 600851475143 es %d\n\n", MAX );
  20.  
  21.    system("pause");
  22.    return 0;
  23. }
  24.  
  25.  

Pero no me da el resultado correcto  :-\

He hecho varios intentos, pero nada...

Saludos.


« Última modificación: 4 Julio 2012, 11:07 am por DickGumshoe » En línea

ralymontes

Desconectado Desconectado

Mensajes: 47



Ver Perfil
Re: Factor primo más grande de un número muy largo
« Respuesta #1 en: 4 Julio 2012, 04:59 am »

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.


En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Factor primo más grande de un número muy largo
« Respuesta #2 en: 4 Julio 2012, 09:07 am »

¡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!
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
DickGumshoe


Desconectado Desconectado

Mensajes: 480



Ver Perfil WWW
Re: Factor primo más grande de un número muy largo
« Respuesta #3 en: 4 Julio 2012, 10:23 am »

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.
En línea

DickGumshoe


Desconectado Desconectado

Mensajes: 480



Ver Perfil WWW
Re: Factor primo más grande de un número muy largo
« Respuesta #4 en: 4 Julio 2012, 11:07 am »

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!  :D

Saludos.
« Última modificación: 4 Julio 2012, 11:09 am por DickGumshoe » En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Factor primo más grande de un número muy largo
« Respuesta #5 en: 4 Julio 2012, 20:02 pm »

¡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
  1. for(i = 2 ; i < numero ; i++)
  2. {
  3.    if(numero % i == 0)
  4.    {
  5.        aux = i;
  6.  
  7.        while(numero % i == 0)
  8.            numero /= i;
  9.    }
  10. }
  11.  
  12. //aux saldra del for con el valor del mayor divisor primo.
  13.  
  14. ¡Saludos!
  15.  
En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
DickGumshoe


Desconectado Desconectado

Mensajes: 480



Ver Perfil WWW
Re: Factor primo más grande de un número muy largo
« Respuesta #6 en: 4 Julio 2012, 20:08 pm »

Muchas gracias, do-while.

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

Saludos.
En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Factor primo más grande de un número muy largo
« Respuesta #7 en: 4 Julio 2012, 20:13 pm »

¡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 pk-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 pk-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;
« Última modificación: 4 Julio 2012, 21:14 pm por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
DickGumshoe


Desconectado Desconectado

Mensajes: 480



Ver Perfil WWW
Re: Factor primo más grande de un número muy largo
« Respuesta #8 en: 4 Julio 2012, 21:47 pm »

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

Saludos.
En línea

do-while


Desconectado Desconectado

Mensajes: 1.276


¿Habra que sacarla de paseo?


Ver Perfil
Re: Factor primo más grande de un número muy largo
« Respuesta #9 en: 5 Julio 2012, 04:01 am »

¡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!
« Última modificación: 5 Julio 2012, 04:05 am por do-while » En línea

- Doctor, confundo los números y los colores.
- Vaya marrón.
- ¿Marrón? ¡Por el culo te la hinco!
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines