Algoritmo de factor primo: C, Python Ejemplo

¿Qué es una factorización prima?

El factor primo de un número es un factor que es en sí mismo un factor primo. número primo, divisible solo por 1 y por sí mismo.

Ejemplo: Los factores primos de 10 son 2 y 5, ya que 2 × 5 = 10.

Encontrar los factores primos usando la iteración

Itera desde 2 hasta sqrt(n) y comprueba la divisibilidad. Mientras n sea divisible por el candidato actual, divide e imprime.

Ejemplo: cada primo mayor que 40 encaja n²+n+41, por lo que n = 0, 1, 2 produce 41, 43, 47.

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

• Itera los números desde 2 hasta sqrt(n).
• Comprueba el módulo de n con respecto a cada candidato; un resto cero significa que el candidato es un factor primo.
• Reúna todos los números primos que dividen a n.
• La rutina se ejecuta con una complejidad temporal de 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 de la criba almacena el factor primo más pequeño de cada número hasta un límite máximo, lo que reduce drásticamente el coste de factorización después del preprocesamiento.

• Registra el factor primo más pequeño de cada número entero hasta el límite máximo.
• Toma ese primo más pequeño y agrégalo al conjunto de factores.
• Divide el número por ese número primo y repite el proceso hasta que llegue a 1.
• Cada consulta se ejecuta en aproximadamente O(log n).

Ejemplo: Un número primo distinto de 2 y 3 se ajusta a la forma 6n-1 o 6n+1. Por ejemplo, 5 = 6(1)-1 y 19 = 6(3)+1.

Algoritmo: definir un matriz que almacena el factor primo más pequeño de cada número, utilizando el índice como valor inicial para cada elemento.

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]

Artículos Relacionados

• Graficar estructura de datos y Algorithms
• Problema de vendedor ambulante
• Algoritmo del método de bisección
• Algoritmo de clasificación de cubos

Python Factores primos usando iteración

Las siguientes Python El código encuentra factores primos utilizando el método iterativo de división por ensayo y error:

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
2
2

Python Factores primos mediante recursividad

El Python El código que aparece a continuación utiliza el método de la criba para encontrar los factores primos de un número dado.

import math
High = (int)(1e5 + 7)
array = [0 for i in range(High)]

# generate smallest prime factors
def Sieve():
    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):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

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

La misma solución iterativa escrita en C: ingrese un número, luego para cada candidato desde 2 hasta sqrt(n), verifique la divisibilidad e imprima cada aparición de un factor primo.

#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

La versión recursiva en C refleja la Python uno: construir el arreglo de los factores primos más pequeños, luego dividir recursivamente por ese factor hasta que n llegue a 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    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)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

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

• Cualquier número par distinto de 2 se puede escribir como la suma de dos números primos (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• No hay números primos consecutivos aparte del 2 y el 3, porque el 2 es el único número primo par.
• Todos los números primos, excepto el 2 y el 3, tienen la forma 6n + 1 o 6n − 1, donde n es un entero positivo.
• El conjunto de factores primos de un número es único.
• El número 1 no es ni primo ni compuesto.
• La factorización prima ayuda con la divisibilidad, la simplificación de fracciones y la búsqueda de denominadores comunes.
• La factorización prima también es la base de los códigos criptográficos basados ​​en números.

Preguntas Frecuentes