Super Simple Python is a series of Python projects you can do in under 15 minutes. In this episode, we’ll be covering how to prime factorize a number in less than 25 lines of Python!

For the video version of making a prime factorizer in Python:

The Super Simple Python series has been pretty focused on simple games and simulators like the Dice Roll Simulator, the High Low Guessing Game, and Rock Paper Scissors. This is the second piece in this series about math after the post about checking if a number is a square.

Check for Factors in Order

How do we do a prime factorization? We simply loop through the numbers less than the square root of our number and divide out all the prime numbers in order. Let’s create a function that takes one parameter, num, that we expect to be an integer.

We’ll start by handling the edge case the num is 1. Why anyone would ever prime factor 1, I have no idea. We’ll start by creating an empty list of factors and starting off the loop at n=2, the smallest prime. Instead of checking if n is less than the square root of num, we’ll check if the square of n is less than or equal to num. While n squared is less than the num we’ll check if the number is divisible by n. If it is, then we will append n to our list of factors and divide num by n. Else, we’ll increment n by one.

At the end of our loop, if num is not 1, then the remaining factor must be prime, and we’ll append that to our list of factors before we return the list.

def prime_factorization(num: int):
    # deal with edge cases
    if num == 1:
        return [1]
    # set up empty list of factors
    factors = []
    # start at 1
    n = 2
    # factor up to sqrt num - there's no prime factors
    # above the sqrt of a number
    while n**2 <= num:
        # check if the number is divisible by the factor
        if num % n == 0:
            factors.append(n)
            num //= n
        else:
            n += 1
    # if we have a number greater than 1 at the end
    # that number is a prime factor
    if num > 1:
        factors.append(num)
   
    return factors

Check some Prime Factorizations

We can really prime factorize any number we want. I chose these 5 for fun. 

print(prime_factorization(225))
print(prime_factorization(1776))
print(prime_factorization(2012))
print(prime_factorization(893))
print(prime_factorization(7392))

When we prime factor these numbers we’ll see an output like the one below.

Final note: we can increment n by 1 each time in the while loop because any non-primes will be skipped automatically, they won’t divide num. My question for you is why? Drop a comment below to let me know.

I run this site to help you and others like you find cool projects and practice software skills. If this is helpful for you and you enjoy your ad free site, please help fund this site by donating below! If you can’t donate right now, please think of us next time.