[Java] Obtener factores primos de un Número

Ejemplo los factores primos de:  600851475143 son:

1
71
839
1471
6857
59569
104441
486847
1234169
5753023
10086647
87625999
408464633
716151937
8462696833

y seguro que falta una mas, por que al ser un numero tan grande lo quite para no esperar hasta el final.

import java.util.*;
public class Ejercicios {

	public static void main(String[] args) {
		
	
	
	 
	 
	 Scanner cin = new Scanner(System.in);
	 long GetPrimo = cin.nextLong();
	int Contador = 0;
	 
	
	for(long i = 1; i <= GetPrimo;i++){
		
		if(GetPrimo % i == 0){
			System.out.println(i);
		}
	}
		
	}
	
	}

Nivel de dificultad: Básico

Vaya!  me paso por la sección de Java y me encuentro con esto, Gracias! 

Hola hackmin,

pues ¿ya has pensado aquí un poco más en cómo optimizar eso?

-> Incremento: ¿Realmente tienes que incrementar i en 1 o se puede optimizar aquí?
-> ¿Hasta donde tienes que probar? ¿Realmente tienes que probar hasta incluído el número?

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!)

Y sobre todo, 1 no es un factor primo.


Saludos

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

Hola hackmin,

si, naturalmente! counter+2 al final. Mientras teclee no puse suficiente atención. (Eso es todo el sentido detrás del código - que a partir del 3 se siga en dos pasos! De lo contrario, lo hubiera hecho un simple counter++;).

Tenía ganas de construir una solución más con la criba de Eratóstenes y, naturalmente, con streams:

        
import static java.util.stream.LongStream.iterate;
import java.util.BitSet;
import java.util.stream.LongStream;
public class PrimeFactors {
  public static void main(String[] args) {
    primeFactors(2 * 2 * 2 * 2 * 2 * 109).forEach(System.out::println);
  }
  public static LongStream primeFactors(int n) {
    BitSet notPrime = new BitSet(n);
    return iterate(2, i -> i <= n, i -> notPrime.nextClearBit((int) (i + 1)))
          .peek(i -> iterate(i * i, j -> j <= n, j -> j + i)
                    .forEach(j -> notPrime.set((int) j, true)))
          .flatMap(i -> iterate(n, j -> (j % i) == 0, j -> j / i)
                       .map(__ -> i));
  }
}

Una vez había algo así en SO (No tienes permitido ver los links. Registrarse o Entrar a mi cuenta


Saludos