# How to Find Prime Factors in Python

Manav Narula Feb 02, 2024

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:

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]
``````
Author: Manav Narula

Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.