How to Find Prime Factors in Python

1. Overview of Prime Factorization
2. Different Approaches to Find Prime Factors in Python

This tutorial will demonstrate how to perform prime factorization in Python.

Overview of Prime Factorization

In mathematics, factors of a number are those numbers that can divide the given number and leave a remainder of zero.

Prime numbers are unique numbers with only two factors, one and the number itself. Some examples of such numbers are 3,7,11,13, and more.

Prime factorization refers to finding all the prime numbers that multiply to make up the original number. We can consider a simple example of the number 6.

The prime factorization of this number yields two factors, 2 and 3.

Different Approaches to Find Prime Factors in Python

We can find prime factors of the specified number in various ways. This article will demonstrate three methods that are listed below:

• Create a custom function
• Use the Sieve of Eratosthenes
• Use the primefac module

Let’s start with creating a custom function in Python.

Custom Function to Perform Prime Factorization

In Mathematics, the most basic prime factorization approach is repeated division. We divide the number by the prime numbers repeatedly. We can implement this in Python using nested loops.

The first loop determines whether a number is a prime number or not. The second loop divides this prime number and the given number.

If the remainder is zero, we append the prime number to a list. The function returns the final list. See the code below.

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

Output:

[2, 2, 5]

In the above example, we returned the prime factorization of 20. The // operator for division ensures that the returned remainder is an integer.

Use the Sieve of Eratosthenes to Perform Prime Factorization

The Sieve of Eratosthenes algorithm returns all the prime numbers below a given number.

It marks the values less than the given number and is divisible by the square of prime numbers to return all prime numbers less than the given number.

We can use it to perform prime factorization in Python. First, we find the prime numbers below the required number, then divide them with the given number to see its prime factorization.

See the following code fence as an example:

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

Output:

[2, 2, 5]

In the above code example, we first create a function that implements the Sieve of Eratosthenes to find the prime numbers below 20.

Then we create another function that uses this list of prime numbers to return the prime factorization of the same.

Use the primefac Module to Perform Prime Factorization

The primefac module is used to perform calculations regarding prime numbers. It can handle extensive calculations efficiently.

We can use this module’s primefac() function for prime factorization. It returns the generator object that can be converted to a list using the list constructor.

See the code below:

import primefac

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

Output:

[2, 2, 5]