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
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))
[2, 2, 5]
In the above example, we returned the prime factorization of
// operator for division ensures that the returned remainder is an integer.
Sieve of Eratosthenes to Perform Prime Factorization
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))
[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
Then we create another function that uses this list of prime numbers to return the prime factorization of the same.
primefac Module to Perform Prime Factorization
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
See the code below:
import primefac print(list(primefac.primefac(20)))
[2, 2, 5]