# Prime factorization program review

Hi!
I’m a beginner at python, and currently self-teaching myself.
I was hoping some of the people here who have more experience than me might take a look at my program and give some advice on how to improve it, any advice would be really appreciated!

Currently I’m working on a code that implements decomposition of any given number into prime factors. Here’s how I wrote it:

First, I create a list of all primes up to the input number (I excluded the input number itself from that list, however due to later problems with certain input numbers being primes themselves, I included the input number)

Then I created loops that continuously tries to divide the input number by the primes in the list, until only 1 remains, by which the loop is conditioned to end. All the primes, through which the input number are divideable, were added to another list which will be printed out as prime factors of the input number.

For the case that the input number is a prime itself (in which case the only prime factor is the input number itself), I’ve added a condition in the end that prints this fact if the prime factors list only has 1 element.

I’ve added the code below, if anyone has any advice as to readability, or any improvements to make it more efficient, or if there are any mistakes, please let me know.
Thanks!!

Here is the code:

``````""" input number that you want prime factorized """
input_num = input(f"Which number do you want to decompose into primes?")
input_num = int(input_num)
prime_numbers = []
prime_factors = []

""" calculates all primes up to input number and adds them to list "prime_numbers" """
for j in range (input_num-1):
prime_check = []
sumpart = j+2
for i in range(sumpart):
divisor = i + 1
if sumpart % divisor == 0:
prime_check.append(divisor)
if len(prime_check)== 2:
prime_numbers.append(sumpart)

""" finds possible factors of the input number in list "prime_numbers", and adds factors to list "prime_factors" """
decomp_num = input_num
while decomp_num != 1:
for prime in prime_numbers:
if decomp_num % prime == 0:
prime_factors.append(prime)
decomp_num = decomp_num / prime
if len(prime_factors) > 1:
print(f"The prime factors of {input_num} are: {prime_factors}")
else:
``````

Have you heard of the Sieve of Eratosthenes? It’s pretty simple, and would save you a lot of trouble in the first phase.

You may also want to consider breaking this down into a few functions.

Quick check: What is the prime factorization of 12, and does your program give the right result?

Keep coding, keep having fun with it!

I notice that you’re dividing `decomp_num` by a prime factor only once. It could occur more than once, e.g. 12 == 3 * 4 * 4. However, as you’re not interested in how many times it occurs, why even bother dividing at all!

The way I’d approach the problem would be to find the first (smallest) prime factor of the number, remove it (it could occur more than once), and then continue with the next prime factor on what’s left. Also, the largest prime factor won’t exceed the square root of the number being tested, i.e. f * f <= n.

Hi Chris, thanks for the feedback!
I did not know about this algorithm (my math knowledge is dusty at best), that’s actually amazing!
I tried to replace my previous algorithm with this, it seems to work but I’m a bit unclear how this improves the program? The sieve, if I understood correctly, creates a list of all integers up to the chosen number, and then systematically removes numbers that are multiples of primes, while the algortihm I previously used checks each integer individually if they fulfill the requirements of being prime.
Is this why the sieve would be more efficient?
Indeed, the program now is faster than before, but I have a hard time conceptualizing why…
I’ve attached the new code here, I still haven’t rewritten the code into functions, but will do so when I have the time!

``````# input number that you want prime factorized
input_num = input(f"Which number do you want to prime factorize?")
input_num = int(input_num)

# calculates all primes up to input number using Sieve of Eratosthenes
number = input_num
prime_factors = []
prime_numbers = []

for i in range(2, number+1):
prime_numbers.append(i)

for num in prime_numbers:
i = 0
y = 0
while y < number:
y = (num**2) + i* num
i += 1
if y in prime_numbers:
prime_numbers.remove(y)

# finds possible factors of the input number in list "prime_numbers", and adds factors to list "prime_factors"
decomp_num = input_num
while decomp_num != 1:
for prime in prime_numbers:
if decomp_num % prime == 0:
prime_factors.append(prime)
decomp_num = decomp_num / prime
if len(prime_factors) > 1:
print(f"The prime factors of {input_num} are: {prime_factors}")
else:
``````

Hi Matthew, thanks for replying, I appreciate it!
Right, I totally did not consider that it just divides through the primes in the list once.

However, the output of the program is still correct, when I e.g. enter 12, it will give me “The prime factors of 12 are: [2, 3, 2]”. Considering the order of the factors, I assume the for loop only adds 2 and 3 to the list, but since decomp_numb is still != 1, the loop repeats again and added another 2 in the second round.

It was actually not really what I originally intended, but it unintentionally seemed to work out ( ofc it would have been better if this was actually what I intended…)

I will try to see if I can implement what you mentioned here, especially with f*f <= n, I could imagine that it could save some unnecessary processing if I can add a condition that stops the loop once Sqrt(n) has been exceded.

Thanks!!

Yeah. Think about what it takes to enumerate the primes up to 100 by each method:

1. Naive method. For every number up to 100, figure out whether it’s prime. For example, to test whether 91 is prime, you have to test `91%2`, `91%3`, `91%4`, `91%5`, `91%6`, `91%7`, and only then do you discover that it’s composite. It’s even worse with 97, since you’ll test a huge number of possible divisors before discovering that it’s actually prime.

2. Sieve of Erastosthenes. For every prime number up to 10, run through all its multiples up to 100. So that means wiping out 49 even numbers, then 33 multiples of three (half of which are already gone, but that’s okay), 20 multiples of 5, 14 multiples of 7, and then… oh we’re done! That’s a bit over 100 tests to find all the primes up to 100, which is a pretty good ratio (much better than 100**2 which is what the naive version can do).

There are a few other advantages too (for instance, most computers can multiply more quickly than divide; plus, the Sieve can be implemented with one single multiplication per prime, and then nothing but addition after that), but this is the biggest one.

It’s definitely worth refactoring this code into functions; once you find the time to do so, you should be able to call a function to get a list of the primes up to some number N, and test that independently of the prime factorization.

But other than that, I think your code is pretty decent. I’d make one small change, partly for performance and partly for aesthetics. You have an outer “while it’s not 1” loop, and inside that, you iterate over all the primes. You could switch those loops around like this:

``````    for prime in prime_numbers:
while decomp_num % prime == 0:
prime_factors.append(prime)
decomp_num = decomp_num / prime
``````

Now you make one single pass over the primes, which is cleaner and easier to think about, and will also run a bit faster. A fairly small change, honestly; for the most part, the code is looking good!