Programa Java para imprimir eficientemente todos los factores primos de un número dado

Dado un número n, escribe una función eficiente para imprimir todos los factores primos de n. Por ejemplo, si el número de entrada es 12, la salida debería ser «2 2 3». Y si el número de entrada es 315, la salida debería ser «3 3 5 7». 
Los siguientes son los pasos para encontrar todos los factores primos. 
1) Mientras que n es divisible por 2, imprima 2 y divida n por 2. 
2) Después del paso 1, n debe ser impar. Ahora inicia un bucle desde i = 3 hasta la raíz cuadrada de n. Mientras i divide n, imprima i y divida n entre i, incremente i en 2 y continúe. 
3) Si n es un número primo y es mayor que 2, entonces n no se convertirá en 1 en los dos pasos anteriores. Entonces imprima n si es mayor que 2.
 

// Program to print all prime factors
import java.io.*;
import java.lang.Math;
 
class GFG {
    // A function to print all prime factors
    // of a given number n
    public static void primeFactors(int n)
    {
        // Print the number of 2s that divide n
        while (n % 2 == 0) {
            System.out.print(2 + " ");
            n /= 2;
        }
 
        // n must be odd at this point.  So we can
        // skip one element (Note i = i +2)
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            // While i divides n, print i and divide n
            while (n % i == 0) {
                System.out.print(i + " ");
                n /= i;
            }
        }
 
        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            System.out.print(n);
    }
 
    public static void main(String[] args)
    {
        int n = 315;
        primeFactors(n);
    }
}

3 3 5 7

Complejidad del tiempo: O(n ^1/2 )

Espacio Auxiliar: O(1)

¿Como funciona esto?  
Los pasos 1 y 2 se encargan de los números compuestos y el paso 3 se ocupa de los números primos. Para probar que el algoritmo completo funciona, necesitamos probar que los pasos 1 y 2 realmente se encargan de los números compuestos. Está claro que el paso 1 se encarga de los números pares. Y después del paso 1, todos los factores primos restantes deben ser impares (la diferencia de dos factores primos debe ser al menos 2), esto explica por qué i se incrementa en 2. Ahora, la parte 
principal es que el ciclo se ejecuta hasta la raíz cuadrada de n, no hasta . Para probar que esta optimización funciona, consideremos la siguiente propiedad de los números compuestos. 
Todo número compuesto tiene al menos un factor primo menor o igual a la raíz cuadrada de sí mismo. 
Esta propiedad se puede probar usando una declaración contraria. Sean a y b dos factores de n tales que a*b = n. Si ambos son mayores que √n, entonces ab > √n, * √n, lo que contradice la expresión “a * b = n”. 
En el paso 2 del algoritmo anterior, ejecutamos un ciclo y hacemos lo siguiente en el ciclo 
a) Encuentra el menor factor primo i (debe ser menor que √n, ) 
b) Elimina todas las ocurrencias i de n dividiendo repetidamente n por i. 
c) Repita los pasos ayb para dividir n e i = i + 2. Los pasos ayb se repiten hasta que n se convierte en 1 o en un número primo.
Consulte el artículo completo sobre el programa eficiente para imprimir todos los factores primos de un número determinado para obtener más detalles.