Algoritmo de factor primo: C, ejemplo de Python

¿Qué es una factorización prima?

El factor primo de un dado cualquier 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é primo numbers multiplicar 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 primos numbers.

Encontrar los factores primos usando la iteración

Para encontrar los factores primos de un número dado, primero iteramos sobre todos los numbers desde 2 hasta la raíz cuadrada del número, y luego verifica si cada número es primo. Mientras el número original sea divisible por este primo, seguiremos sumando este primo con cada iteración.

Ejemplo:

Cada número primo mayor que 40 se escribe de la siguiente manera.wing fórmula: norte2+n+41. Entonces, podemos sustituir n con todos los numbers para encontrar el factor primo correspondiente. por ejemplo, 02+0+41=41, 12+1+41=43, 22+2+41=47,…

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

  • En este método, iteraremos sobre el numbers desde 2 hasta la raíz cuadrada del número, como se mencionó en el apartado anterior.
  • Para eso, necesitamos verificar el módulo del número original en cada uno de los numbers desde 2 hasta la raíz cuadrada de n .
  • Luego encontramos la lista de primos. numbers que son factores de n.
  • Esta solución está en tiempo O(Sqrt(n)) complexity.

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 de tamiz se basa en almacenar el factor primo más pequeño de la numbers, lo que reduce la complexidad notablemente al calcular los factores primos de cualquier número. El algoritmo de tamiz encuentra todos los factores primos de manera algo eficiente.

  • 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 O(log(n)) tiempo complexidad, mejorando mucho la eficiencia de la solución.
  • Lo que permite calcular los factores primos de números mucho mayores. numbers que los que podríamos haber abordado 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]

Factores primos de Python usando iteración

Aquí estaremos showing un código en lenguaje Python 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

Factores primos de Python mediante recursividad

Esta sección muestra un código en Lenguaje python 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

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 Prime numbers

  • Uno de los hechos más interesantes es que cualquier número par distinto de 2 puede ser la suma de dos números primos. numbers.
  • 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 principales numbers excepto 2 y 3 se pueden escribir a continuaciónwing forma: 6 * n + 1 o 6 * n – 1, donde n es un número entero positivo.
  • El conjunto de factores primos de un número es único.
  • El número 1 no es primo ni compuesto.
  • Factorización prima de numbers 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.