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

Dado un número n , escriba una función eficiente para imprimir todos los factores primos de n . Por ejemplo, si el número de entrada es 12, entonces la salida debería ser «2 2 3». Y si el número de entrada es 315, entonces la salida debería ser «3 3 5 7».

Primer enfoque:

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. Después de que no pueda dividir n, 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 por los dos pasos anteriores. Entonces imprima n si es mayor que 2. 

// C++ program to print all prime factors
#include <bits/stdc++.h>
using namespace std;
 
// A function to print all prime
// factors of a given number n
void primeFactors(int n)
{
    // Print the number of 2s that divide n
    while (n % 2 == 0)
    {
        cout << 2 << " ";
        n = n/2;
    }
 
    // n must be odd at this point. So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i + 2)
    {
        // While i divides n, print i and divide n
        while (n % i == 0)
        {
            cout << i << " ";
            n = n/i;
        }
    }
 
    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        cout << n << " ";
}
 
/* Driver code */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}
 
// This is code is contributed by rathbhupendra

// Program to print all prime factors
# include <stdio.h>
# include <math.h>
 
// A function to print all prime factors of a given number n
void primeFactors(int n)
{
    // Print the number of 2s that divide n
    while (n%2 == 0)
    {
        printf("%d ", 2);
        n = n/2;
    }
 
    // n must be odd at this point.  So we can skip
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(n); i = i+2)
    {
        // While i divides n, print i and divide n
        while (n%i == 0)
        {
            printf("%d ", i);
            n = n/i;
        }
    }
 
    // This condition is to handle the case when n
    // is a prime number greater than 2
    if (n > 2)
        printf ("%d ", n);
}
 
/* Driver program to test above function */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

// 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 when
        // 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);
    }
}

# Python program to print prime factors
 
import math
 
# A function to print all prime factors of
# a given number n
def primeFactors(n):
     
    # Print the number of two's that divide n
    while n % 2 == 0:
        print 2,
        n = n / 2
         
    # n must be odd at this point
    # so a skip of 2 ( i = i + 2) can be used
    for i in range(3,int(math.sqrt(n))+1,2):
         
        # while i divides n , print i and divide n
        while n % i== 0:
            print i,
            n = n / i
             
    # Condition if n is a prime
    # number greater than 2
    if n > 2:
        print n
         
# Driver Program to test above function
 
n = 315
primeFactors(n)
 
# This code is contributed by Harshit Agrawal

// C# Program to print all prime factors
using System;
 
namespace prime
{
public 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)
        {
            Console.Write(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)
            {
                Console.Write(i + " ");
                n /= i;
            }
        }
 
        // This condition is to handle the case whien
        // n is a prime number greater than 2
        if (n > 2)
            Console.Write(n);
    }
     
    // Driver Code
    public static void Main()
    {
        int n = 315;
        primeFactors(n);
    }
 
}
}
 
// This code is contributed by Sam007

<?php
// PHP Efficient program to print all
// prime factors of a given number
 
// function to print all prime
// factors of a given number n
function primeFactors($n)
{
     
    // Print the number of
    // 2s that divide n
    while($n % 2 == 0)
    {
        echo 2," ";
        $n = $n / 2;
    }
 
    // n must be odd at this
    // point. So we can skip
    // one element (Note i = i +2)
    for ($i = 3; $i <= sqrt($n);
                   $i = $i + 2)
    {
         
        // While i divides n,
        // print i and divide n
        while ($n % $i == 0)
        {
            echo $i," ";
            $n = $n / $i;
        }
    }
 
    // This condition is to
    // handle the case when n
    // is a prime number greater
    // than 2
    if ($n > 2)
        echo $n," ";
}
 
    // Driver Code
    $n = 315;
    primeFactors($n);
 
// This code is contributed by aj_36
?>

<script>
 
// JavaScript program to print all prime factors
 
// A function to print all prime
// factors of a given number n
function primeFactors(n)
{
     
    // Print the number of 2s that divide n
    while (n % 2 == 0)
    {
        document.write(2 + " ");
        n = Math.floor(n / 2);
    }
 
    // n must be odd at this point.
    // So we can skip one element
    // (Note i = i +2)
    for(let i = 3;
            i <= Math.floor(Math.sqrt(n));
            i = i + 2)
    {
         
        // While i divides n, print i
        // and divide n
        while (n % i == 0)
        {
            document.write(i + " ");
            n = Math.floor(n / i);
        }
    }
 
    // This condition is to handle the
    // case when n is a prime number
    // greater than 2
    if (n > 2)
        document.write(n + " ");
}
 
// Driver code
let n = 315;
 
primeFactors(n);
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Producción: 

3 3 5 7

Complejidad de tiempo: O(n^(1/2) log n)

Dado que el bucle externo se ejecuta por sqrt(n) veces y para cada bucle estamos dividiendo n entre i , lo que nos da una complejidad de tiempo logarítmica.

Espacio Auxiliar: O(1)

¿Como funciona esto?  
Los pasos 1 y 2 se encargan de los números compuestos y el paso 3 se encarga 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 bucle se ejecuta hasta la raíz cuadrada de n, no hasta n. 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 que la raíz cuadrada de sí mismo.  
Esta propiedad se puede probar usando una contra declaración. 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) Encuentre el menor factor primo i (debe ser menor que √n,) 
b) Quite 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.

Segundo enfoque: este enfoque es similar al Tamiz de Eratóstenes.

Podemos lograr O (log n) para todos los números compuestos mediante la división consecutiva del número dado por un número entero a partir de 2 que representa el factor actual de ese número. Este enfoque se basa en el hecho de que todos los números compuestos tienen factores en pares que no sean 1 o el número en sí mismo, como 6 = 3 x 2 y 9 = 3 x 3, mientras que para los números primos no existe tal par más que 1 o el número en sí.

Por lo tanto, si comenzamos a dividir el número por el número primo más pequeño posible (2), todos sus múltiplos o números compuestos se eliminarán automáticamente antes de llegar a ese número.

Ejemplo: podemos dividir 12 por 2 dos veces y eliminar esos factores de 12 para obtener 3, asegurándonos así de que el número compuesto 4 (múltiplo de 2) no ocurra en ningún momento posterior.

De manera similar, si tenemos un número grande que no es divisible por ningún valor de c=2 a n-1, significa que es primo como 13 (no divisible de 2 a 12).

#include <bits/stdc++.h>
using namespace std;
 
void primeFactors(int n)
{
    int c=2;
    while(n>1)
    {
        if(n%c==0){
        cout<<c<<" ";
        n/=c;
        }
        else c++;
    }
}
 
/* Driver code */
int main()
{
    int n = 315;
    primeFactors(n);
    return 0;
}

#include <stdio.h>
 
void primeFactors(int n)
{
  int c = 2;
  while (n > 1) {
    if (n % c == 0) {
      printf("%d ", c);
      n /= c;
    }
    else
      c++;
  }
}
 
/* Driver code */
int main()
{
  int n = 315;
  primeFactors(n);
  return 0;
}
 
// This code is contributed by Rohit Pradhan

import java.util.*;
class GFG {
    public static void primeFactors(int n)
    {
        int c = 2;
        while (n > 1) {
            if (n % c == 0) {
                System.out.print(c + " ");
                n /= c;
            }
            else
                c++;
        }
    }
 
    /* Driver code */
    public static void main(String[] args)
    {
        int n = 315;
        primeFactors(n);
    }
}
 
// This code is contributed by Taranpreet

using System;
class GFG {
    static void primeFactors(int n)
    {
        int c = 2;
        while (n > 1) {
            if (n % c == 0) {
                Console.Write(c + " ");
                n /= c;
            }
            else
                c++;
        }
    }
    /* Driver code */
    public static int Main()
    {
        int n = 315;
        primeFactors(n);
        return 0;
    }
}
// This code is contributed by Taranpreet

def primeFactors(n):
 
    c = 2
    while(n > 1):
 
        if(n % c == 0):
            print(c, end=" ")
            n = n / c
        else:
            c = c + 1
 
# Driver code
n = 315
primeFactors(n)
 
# This code is contributed by Taranpreet

<script>
function primeFactors(n)
{
    let c = 2;
    while(n > 1)
    {
        if(n % c == 0){
            document.write(c + " ");
            n /= c;
        }
        else c++;
    }
}
 
/* Driver code */
let n = 315;
primeFactors(n);
 
// This code is contributed by singhh3010.
</script>

Complejidad de tiempo: este enfoque es mejor para todos los números compuestos y logra O (log n) pero es O (n) de lo contrario.

Espacio Auxiliar: O(1)

Artículo relacionado: 
Factorización prima usando Sieve O(log n) para consultas múltiples
Gracias a Vishwas Garg por sugerir el algoritmo anterior. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.