Encuentra factores primos en Python

1. Descripción general de la factorización prima
2. Diferentes enfoques para encontrar factores primos en Python

Este tutorial demostrará cómo realizar la factorización prima en Python.

Descripción general de la factorización prima

En matemáticas, los factores de un número son aquellos números que pueden dividir el número dado y dejar un resto de cero.

Los números primos son números únicos con solo dos factores, uno y el número en sí. Algunos ejemplos de tales números son 3,7,11,13 y más.

La factorización prima se refiere a encontrar todos los números primos que se multiplican para formar el número original. Podemos considerar un ejemplo simple del número 6.

La factorización prima de este número produce dos factores, 2 y 3.

Diferentes enfoques para encontrar factores primos en Python

Podemos encontrar factores primos del número especificado de varias maneras. Este artículo demostrará tres métodos que se enumeran a continuación:

• Crear una función personalizada
• Usa el Tamiz de Eratóstenes
• Utilizar el módulo primefac

Comencemos con la creación de una función personalizada en Python.

Función personalizada para realizar factorización prima

En Matemáticas, el enfoque de factorización prima más básico es la división repetida. Dividimos el número entre los números primos repetidamente. Podemos implementar esto en Python usando bucles anidados.

El primer ciclo determina si un número es un número primo o no. El segundo bucle divide este número primo y el número dado.

Si el resto es cero, agregamos el número primo a una lista. La función devuelve la lista final. Vea el código a continuación.

def p_factorization(n):
    i = 2
    lst = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            lst.append(i)
    if n > 1:
        lst.append(n)
    return lst


print(p_factorization(20))

Producción :

[2, 2, 5]

En el ejemplo anterior, devolvimos la descomposición en factores primos de 20. El operador // para la división garantiza que el resto devuelto sea un número entero.

Usa el Tamiz de Eratóstenes para realizar la factorización prima

El algoritmo Tamiz de Eratóstenes devuelve todos los números primos por debajo de un número dado.

Marca los valores menores que el número dado y es divisible por el cuadrado de los números primos para devolver todos los números primos menores que el número dado.

Podemos usarlo para realizar la factorización prima en Python. Primero, encontramos los números primos debajo del número requerido, luego los dividimos con el número dado para ver su descomposición en factores primos.

Vea la siguiente valla de código como ejemplo:

def sieve_of_erast(number):
    maximum = number + 1
    d = dict()
    for i in range(2, maximum):
        d[i] = True

    for i in d:
        factors = range(i, maximum, i)
        for f in factors[1:]:
            d[f] = False
    lst = [i for i in d if d[i] == True]
    return lst


def p_factorization(number):
    x = number
    res = []
    lst = sieve_of_erast(number)
    i = 0
    while i < len(lst):
        if x % lst[i] == 0:
            x = x // lst[i]
            res.append(lst[i])
            i = 0
            if x == 1:
                break
        else:
            i = i + 1
    return res


print(p_factorization(20))

Producción :

[2, 2, 5]

En el ejemplo de código anterior, primero creamos una función que implementa el Tamiz de Eratóstenes para encontrar los números primos debajo de 20.

Luego creamos otra función que usa esta lista de números primos para devolver la descomposición en factores primos de los mismos.

Use el módulo primefac para realizar la factorización prima

El módulo primefac se utiliza para realizar cálculos con números primos. Puede manejar cálculos extensos de manera eficiente.

Podemos usar la función primefac() de este módulo para la factorización prima. Devuelve el objeto generador que se puede convertir en una lista usando el constructor lista.

Vea el código a continuación:

import primefac

print(list(primefac.primefac(20)))

Producción :

[2, 2, 5]