Project Euler ->Problema 3

Dice así:

Los factores primos de 13195 son: 5, 7, 13, y 29.
Cuál es el factor primo más grande del número 600851475143?

Ok el primer problema fue: Qué re diantres son los factores primos… (no me acordaba😯 )hasta que busqué en wikipedia y listoco.

Código después del salto ->OK como es un poco enredado, vamos con el estrujamiento cerebral:

  • Cuando dividimos por el factor, el número se va achicando. El último valor es el mismo número por el que están dividiendo, por lo que da 1.
    Por ejemplo, si tenemos el 50: 50/2 = 25 | 25/5 = 5 | 5/5 = 1
    Entonces, tenemos que parar cuando el resultado sea 1, que si no se va a las pailas  todo😯
  • Como vieron arriba, la única forma de aumentar el factor es que ya no se pueda dividir por él. Onda un ciclo😉
  • El tema de los factores es igual a que cuando queremos saber si un número es par, por eso la idea es que el resto de la división sea 0 (eso que queda abajo xD).
  • La primera idea que se me vino era haciendo una función que se llamara a sí misma (aka recursiva). Pero después mutó en 2 ciclos: un for y un while😀

Estuve como 2 días tratando de hacerlo xD porque no me salía. Y cuando por fin llegué a un resultado, fue por error. Al principio no controlé el tema del 1, por lo que me seguía dividiendo y me daba un StackOverFlow x_X y se colgaba justo antes de dividir por el último factor (así que lo hice yo a mano y me dio xDDD)😯

El ciclo while divide por el factor. El único corte que tiene es que el resto sea 0. Si lo es, sigue dividiendo por el mismo factor y reemplazando el número (por el resultado) hasta que cambie el resto. Cuando cambia, sale del ciclo y vuelve al for, que controla el valor del factor (la primera vez en 2, la segunda en 3, y así).
Lo último, es que como es un for, se corta en el valor que sigue del factor, por lo que tenemos que retroceder en el tiempo una vez para tener el valor correcto (usando –factor, que viene siendo una resta, mientras “usa” el valor original).

El código sigue abajo en la versión controlada:

public class Problema3 {
    public Problema3(){
        Long numero = 600851475143l;
        Integer factor;
        for (factor = 2; numero > 1; factor++) {
            while(numero % factor == 0){
                numero = numero / factor;
            }
        }
        System.out.println(--factor);
    }
}

Tataaaaan

Acerca de MaritoCares

Ingeniero Informático. Con tendencias a la programación en [C#, VB].NET, Java(Web principalmente...), PHP, JavaScript, algo mínimo de [ruby, python], y el clásico C.
Esta entrada fue publicada en Java, Problemas Project Euler. Guarda el enlace permanente.

6 respuestas a Project Euler ->Problema 3

  1. Java ayuda bastante, pero si se desea usar C/C++, ¿que alternativa conoces para esos casos?

  2. turitersa dijo:

    /*Los factores primos de 13195 son: 5, 7, 13, y 29.
    Cuál es el factor primo más grande del número 600851475143?*/
    #include
    using namespace std;
    main()
    {long long max=0,n;
    cout<>n;
    for(long long j=1;j<=n;j++)
    {if(n%j==0)
    {long long c=0;
    for(long long i=1;imax)
    max=j;
    }
    }
    }
    cout<<"el factor primo mas grande es : "<<max;
    }

  3. Elll dijo:

    Che al final cual es la respuesta correcta, yo lo hice en java me da que el numero “600851475143”
    es primo en si. Puse eso como respuesta y me da que mi solucion es incorrecta.

  4. Anónimo dijo:

    por que hay que ponerle la “l” a 600851475143?

    • MaritoCares dijo:

      Hola!
      Para que el motor “entienda” que es un Long.
      Por el largo debería ser suficiente … pero al menos en ese año (2010), netBeans no entendía si únicamente le escribía el número y lo marcaba como error🙂

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s