Algoritmo de factor primo: C, Python Ejemplo

¿Qué es una factorización prima?

El factor primo de un dado any El número es el factor que es un número primo. Los factores cuando se multiplican dan otro número. Un número primo es divisible por sí mismo o por 1.

En otras palabras, los factores primos se determinan encontrando qué números primos se multiplican entre sí para formar el número original.

Ejemplo:Los factores primos de 10 son 2 y 5. Esto se debe a que 2X5 = 10 y ambos 2,5 son números primos.

Encontrar los factores primos usando la iteración

Para encontrar los factores primos de un número dado, primero iteramos sobre todos los números desde 2 hasta la raíz cuadrada del número y luego verificamos si cada número es primo. Siempre que el número original sea divisible por este primo, seguimos sumando este primo en cada iteración.

Ejemplo:

Todo número primo mayor que 40 se escribe con la siguiente fórmula: n²+n+41. Por lo tanto, podemos sustituir n por todos los números para encontrar el factor primo correspondiente, por ejemplo, 0.²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

¿Cómo imprimir un factor primo de un número?

• En este método, iteraremos sobre los números desde 2 hasta la raíz cuadrada del número, como se mencionó en la sección anterior.
• Para ello, necesitamos comprobar el módulo del número original en cada uno de los números desde 2 hasta la raíz cuadrada de n.
• Luego, encontramos la lista de números primos que son factores de n.
• Esta solución tiene una complejidad de tiempo O(Sqrt(n)).

Algoritmo:

Set a counter i  to 2
While i  <= sqrt(n):
	While n% i  == 0:
		n = n / i  
		print i  
	i  = i  +1
if n > 1:
	print n

Algoritmo de tamiz

El método Sieve se basa en almacenar el factor primo más pequeño de los números, lo que reduce notablemente la complejidad al calcular los factores primos de cualquier número. El algoritmo Sieve encuentra todos los factores primos con relativa eficiencia.

• El concepto principal de este algoritmo es almacenar el factor primo más pequeño de cada número hasta el número máximo.
• Tomamos el primo más pequeño de cada número dado y lo sumamos al conjunto de factores primos.
• Finalmente, dividimos por este número primo y repetimos estos pasos hasta llegar a 1.
• Todo esto se hace en una complejidad de tiempo O(log(n)), lo que mejora mucho la eficiencia de la solución.
• Lo que permite calcular los factores primos de números mucho mayores que los que podríamos haber manejado utilizando el enfoque anterior.

Ejemplo:

La segunda forma es comprobar si el número se puede escribir como 6n-1 o 6n+1, ya que cualquier número primo distinto de 2 y 3 debe escribirse en una de las dos fórmulas. por ejemplo, 5=6(1)-1, 19=6(3)+1,….

Algoritmo:

Defina una matriz para almacenar el factor primo más pequeño de cada número con el valor del índice como valor inicial para cada elemento del matriz.

Set array[1] to 1
Set i to 2
While i*i > max number:
	If array[i] == i:
		Set j to i*i
		While j > max number:
			If array[j] == j:
				Array[j] = i
			j = j + i
	i = i + 1
while the number != 1:
	print array[the number]
	the number = the number / array[the number]

Python Factores primos usando iteración

Aquí mostraremos un código en Python lenguaje para encontrar los factores primos de un número dado en un método iterativo:

import math
def PrimeFactors(n):
    for i in range(2,int(math.sqrt(n))+1,1):
        while n%i==0:#find all the occurrences of a prime factor
            print((int)(i)),
            n=n/i
    if n!=1:#if the number was originally a prime
        print((int)(n))
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

Salida:

Enter the number you want: 4
4

Python Factores primos mediante recursividad

Esta sección muestra un código en Python idioma usando el método del tamiz para encontrar los factores primos de un número dado.

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    for i in range(1, High):
        array[i]=i
    for i in range(2, math.ceil(math.sqrt(High))):
        if (array[i] == i):
            for j in range(i*i, High,i):
                if(array[j]==j):
                    array[j]=i
def PrimeFactors(n):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

Salida:

Enter the number you want: 4
2
2

Programa de factores primos C mediante iteración

Es la misma solución que la iterativa de Python pero escrita en Lenguaje C.

Le pedimos al usuario que ingrese el número, luego, para cada número desde 2 hasta la raíz cuadrada de este número, debemos verificar si es divisible imprimiendo todas las apariciones de este factor.

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for(int i=2; i*i<=n; i++)
    {
        while(n%i==0)//find all the occurrences of a prime factor
        {
            printf("%d\n",i);
            n/=i;
        }
    }
    if(n!=1)//if the number was originally a prime
    {
        printf("%d",n);
    }
    return 0;
}

Salida:

Enter the number you want: 2
2

Programa de factores primos C mediante recursividad

Esta es la misma solución que la recursiva de Python pero escrita en C.

Podemos pedirle al usuario que ingrese el número; luego, construimos la matriz de números primos que almacena el factor primo más pequeño de cada número. Finalmente, llamamos función recursiva de factores primos, que divide el número dado por su factor primo más pequeño y se recupera hasta llegar a uno.

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    for(int i=1;i<Max;i++)
    {
        array[i]=i;
    }
    for(int i=2;i*i<=Max;i++)
    {
        if(array[i]==i)
        {
            for(int j=i*i;j<Max;j+=i)
            {
                if(array[j]==j)
                {
                    array[j]=i;
                }
            }
        }
    }
}
void PrimeFactors(int n)
{
    if(n==1)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

Salida:

Enter the number you want: 2
2

Algunos datos interesantes sobre los números primos

• Uno de los datos más interesantes es que cualquier número par distinto de 2 puede ser la suma de dos números primos.
• Por ejemplo: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3…etc.
• Otro hecho es que no hay primos consecutivos distintos del 2 y el 3, ya que el único número primo par es el número 2.
• Además, todos los números primos excepto 2 y 3 se pueden escribir en la siguiente forma: 6 * n + 1 o 6 * n – 1, donde n es un entero positivo.
• El conjunto de factores primos de un número es único.
• El número 1 no es primo ni compuesto.
• La factorización prima de números puede ayudar a resolver problemas como divisibilidad, simplificar fracciones y encontrar denominadores comunes de diferentes fracciones.
• Además, uno de los usos interesantes de la factorización prima es descifrar códigos secretos basados ​​en números.