Super Simple Python: Prime Factorization

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.

Learn More

To learn more, feel free to reach out to me @yujian_tang on Twitter, connect with me on LinkedIn, and join our Discord. Remember to follow the blog to stay updated with cool Python projects and ways to level up your Software and Python skills! If you liked this article, please Tweet it, share it on LinkedIn, or tell your friends!

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.

Yujian Tang
Yujian Tang

I started my professional software career interning for IBM in high school after winning ACSL two years in a row. I got into AI/ML in college where I published a first author paper to IEEE Big Data. After college I worked on the AutoML infrastructure at Amazon before leaving to work in startups. I believe I create the highest quality software content so that’s what I’m doing now. Drop a comment to let me know!

One-Time
Monthly
Yearly

Make a one-time donation

Make a monthly donation

Make a yearly donation

Choose an amount

$5.00
$15.00
$100.00
$5.00
$15.00
$100.00
$5.00
$15.00
$100.00

Or enter a custom amount

$

Your contribution is appreciated.

Your contribution is appreciated.

Your contribution is appreciated.

DonateDonate monthlyDonate yearly

One thought on “Super Simple Python: Prime Factorization

Leave a Reply

%d bloggers like this: