Vaya! ;D me paso por la sección de Java y me encuentro con esto, Gracias! 8) ;D
Hola hackmin,
y no tienes que reinventar la rueda. Alimentar un motor de busqueda con "Java prime factor given number" hubiera sacado a la luz algunas ideas (mas eficientes).
Lamentablemente calculas todos los divisores aunque se trata de factores primos. Por lo tanto, de nuevo mi indicio:
Citar
Si opinas tener un algoritmo: Pues ¿suministra el números correctos? (¡Aquí se prueba con números pequeños que también se pueden verificar a mano y así! ¡Por tanto prueba una vez tu algoritmo p. e. con el número 8!)
Edición: Aunque aquí 8 ya bastaría, 8! Ya es algo grande.
Osea, por un lado se tiene que verificar 2, naturalmente. Entonces se puede seguir con 3 en dos pasos.
Si se tiene un divisor, entonces se verifica si el divisor se repite múltiples de veces. Por lo tanto se debe dividir el número por el divisor y luego seguir con el resultado. De allí que sugerí el 8 como ejemplo.
8%2 = 0 -> 2 es un divisor, 8/2 = 4.
Verificamos 4 de nuevo - 4%2 = 0 -> Es un divisor, 4/2 = 2
Verificamos 2 de nuevo - 2%2 = 0 -> Es nuevamente un divisor, 2/2 = 1 -> Final.
Factorización en números primos de 8 es, por consiguiente, 2,2,2.
Por tanto, que se puede identificar en este ejemplo?:
a) Si se ha encontrado un divisor, el final siempre se desplaza.
b) Se debe verificar un divisor múltiples de veces.
c) El final se tiene que definir. Aquí se puede proceder fácilmente: Contador -> Raíz del número restante -> En ese caso es el número restante el último divisor. Osea en el ejemplo tuvimos número restante 4, contador 2 -> Éxito, nuevo número restante 2, prueba: 2> Raiz de 2: ==> Número restante es el último divisor.
Quizás se puede todavía pensar que se prueba: Número restante == Contador ->. En ese caso se ahorra una vez la raíz. Pero esa optimización no la veo como algo tan alucinante porque complica un poco el algoritmo y, en mi opinión, no satisface el principio KISS.
Con esto, ojala que esto esté claro:
Fraccionamiento en factores primos.
El posible algoritmo.
Y si ya lo he puesto tan lejos como pretexto, entonces también puedo dar un ejemplo de implementación:
import java.util.ArrayList;
import java.util.List;
public class PrimeFactor {
public static List<Long> getPrimeFactors(final long number) {
List<Long> result = new ArrayList<>();
long counter = 2;
long reminder = number;
while (counter < Math.sqrt(reminder)) {
while (reminder % counter == 0) {
result.add(counter);
reminder=reminder/counter;
}
counter = (counter==2) ? 3 : counter+1;
}
if (reminder > 1) {
result.add(reminder);
}
return result;
}
public static void main(String[] args) {
System.out.println("8 fraccionado: " + getPrimeFactors(8));
System.out.println("600851475143 fraccionado: " + getPrimeFactors(600851475143L));
}
}
Y esto, naturalmente, calcula muy rápido los resultados:
8 fraccionado: [2, 2, 2]
600851475143 fraccionado: [71, 839, 1471, 6857]
Saludos