Python Prime Factorization – Find Prime Factors of Number

Prime factorization is easy to do in Python. We can find the prime factors of a number by defining a function, applying some logic to get the prime factors, and returning a list of the prime factors.

Below is a function which will get the prime factorization of a number in Python.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors

Prime factorization is a way of expressing a number as a product of its prime factors. A prime factor is a prime number, and prime factorization is the process to get all of the numbers which when multiplied equals the given number.

In Python, we can write our own function to find the prime factors of any positive integer. We will be using the division method to find prime factors.

To get the prime factors of a number, we need to do the following:

First, if the given number is even, then we know 2 is a prime factor and we should divide the given number by 2. Until the number is odd, then we should continue dividing by 2.

Next, the temporary number that we are dividing will be odd, and we need to loop through the odd numbers 3 until the square root of the temporary number to see if there are any numbers which can divide our temporary number.

Why are we doing this?

First, we only need to check odd numbers because we’ve taken out all of the even factors in the first step. Second, we only need to check until the square root of the temporary number because of the statement: Every composite number has at least one prime factor less than or equal to the square root of itself.

Finally, if the temporary number is greater than 2, then we know the temporary number is prime (i.e. not composite) and should be added to our list.

Below is the final function to find the prime factors of a given number using Python.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors

Finding Prime Factorization of Numbers Using Python

We can now use our function for prime factorization above to find the prime factorization of some different numbers.

Let’s find the prime factorization of a handful of numbers in the following example.

def prime_factorization(n):
    prime_factors = []
    while (n % 2 == 0):
        n = n / 2
        prime_factors.append(2)
    for i in range(3, int(n**0.5 + 1), 2):
        while (n % i == 0):
            n = n / i
            prime_factors.append(i)
    if n > 2:
        prime_factors.append(int(n))
    return prime_factors
        
print(prime_factorization(10))
print(prime_factorization(13))
print(prime_factorization(90))
print(prime_factorization(121))
print(prime_factorization(749))
print(prime_factorization(283))

#Output:
[2, 5]
[13]
[2, 3, 3, 5]
[11, 11]
[7, 107]
[283]

Hopefully this article has been useful for you to learn how to do prime factorization of numbers in Python.