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.

#### Make a one-time donation

#### Make a monthly donation

#### Make a yearly donation

Choose an amount

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”