Prime Factorization | How to Find Prime Factors of a Number in Python

Introduction

In this article, we will see a python program to print all the prime factors of the given number. If a number is a prime number and perfectly divides the given number then that number is said to be a prime factor of the given number. Here, we will see what is a prime factor, a method to find a prime factor, and the python program.

What is a prime factor of a number?

Prime factors of a number are the prime number which on multiplying together gives the number. we can check the prime factor of a number by two conditions:

  • The number should be a prime number.
  • The number should divide the number perfectly.
python prime factor of a number

Steps to find the prime factors of a number

  1. Let the number be denoted by num.
  2. while num is divisible by 2, we will print 2 and divide the num by 2.
  3. After step 2, num must be always odd.
  4. Start a loop from I = 3 to the square root of n. If i divide num, print i, and divide num by i. After i fail to divide num, increment the i value by 2 and continue.
  5. If num is a prime number and is greater than 2, then the num cannot become 1.
  6. So, print num if it is greater than 2.

Examples of Printing the Prime Factors of a Number in Python

Let us understand the program for prime factors of the number in details with the help of different examples:

1. Prime Factor of a number in Python using While and for loop

In this program, We will be using while loop and for loop both for finding out the prime factors of the given number. we will import the math module in this program so that we can use the square root function in python. After that, we will apply the loop and try to find the prime factors of the given number.

# python program to print prime factors

import math
def primefactors(n):
   #even number divisible
   while n % 2 == 0:
      print (2),
      n = n / 2
   
   #n became odd
   for i in range(3,int(math.sqrt(n))+1,2):
    
      while (n % i == 0):
         print (i)
         n = n / i
   
   if n > 2:
      print (n)

n = int(input("Enter the number for calculating the prime factors :\n"))
primefactors(n)

Output:

Enter the number for calculating the prime factors :
650
2
5
5
13

Explanation:

Here firstly we have imported the math library from the python module. Secondly, we have taken the input n as the number and called the function primefactors(). Thirdly, we have taken primefactors() as the function and applied while loop and checked if the modulo of the number is coming 0 by dividing it by 2. Fourthly, the while loop will be executed till the number is even and divisible by 2 and printing it and divide the number by 2 at each iteration. After that, we will apply the for loop from ‘i=3’ till the square root of n+1. Then again we will apply while loop inside the for loop and check the condition. At last, if n is greater than 2 then we have printed the number. Hence, all the prime factors of the number get printed.

2. using for loop only

In this program, We will be using for loop only for finding out the prime factors of the given number. we will be applying multiple for loops and try to find the prime factors of the given number.

#using for loop

n = int(input("Enter the number for calculating the prime factors :\n"))
for i in range(2,n + 1):
    if n % i == 0:
        count = 1
        for j in range(2,(i//2 + 1)):
            if(i % j == 0):
                count = 0
                break
        if(count == 1):
            print(i)

Output:

Enter the number for calculating the prime factors :
350
2
5
7

Explanation:

In this example, we will be using for loop only. Firstly, we have taken the input from the user as n. Secondly, we have applied the for loop from i=2 to i=n+1. Then, we will check if the modulo of the value of i and number is equal to 0. Then we keep the count value = 1 and again apply the for loop inside the for loop from j=2 to j=i//2+1. and check the given if condition. if the condition satisfies count value is set to 0 and we break the statement. We come out of the for loop and check the condition if count ==1 and print the value of i. hence the primefactors are printed with the single-single value of them.

NOTE:

Suppose we take input as 650 : the prime factors are 2,5,5,13
so, it will print 2,5,13 as all integers one time.

3. Prime Factor Of A Number In Python using while loop only

In this program, We will be using a while loop only for finding out the prime factors of the given number. we will be applying multiple while loops and try to find the prime factors of the given number.

#using while loop

n = int(input("Enter any Number for calculating the prime factors: "))
i = 1

while(i <= n):
    c = 0
    if(n % i == 0):
        j = 1
        while(j <= i):
            if(i % j == 0):
                c = c + 1
            j = j + 1
            
        if (c == 2):
            print(i)
    i = i + 1

Output:

Enter any Number for calculating the prime factors: 350
2
5
7

Explanation:

In this example, we will be using a while loop only. Firstly, we have taken the input from the user as n. Secondly, we will set i value as 1. Thirdly, we will apply a while loop with checking condition as i should be less than or equal to n. Inside the loop, we will set the c value as 0 and apply the if and while the condition in it. At last, we will be checking if the value of c becomes equal to 2 then we print the value of i. hence, the prime factors are printed with the single-single value of them.

NOTE:

Suppose we take input as 650 : the prime factors are 2,5,5,13
so, it will print 2,5,13 as all integers one time.

Conclusion

In this tutorial, we have seen how to find the prime factors of the number with 3 different methods. All the methods are explained in detail with the help of examples and their explanation. You can use any method which you like according to your need.

Subscribe
Notify of
guest
20 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
RichardMC
RichardMC
2 years ago

the third method does not work for the number 100

Pratik Kinage
Admin
2 years ago
Reply to  RichardMC

No, it works perfectly fine. The output for number 100 comes as 2 and 5. Since 22*52 == 100, the output correct.

RichardMC
RichardMC
2 years ago

Hello,
I already understood the result of the program.

I thought that for the number 100 the output was:
2
2
5
5
The program displays the prime factors but only once, not the number that is repeated in the factorial decomposition.

Pratik Kinage
Admin
2 years ago
Reply to  RichardMC

Yes, you can do this by using a small loop inside the if(c==2) statement –

k = n
while(k%i==0):
k/=i
print(i)

For 100, the output will become 2 2 5 5.

Regards,
Pratik

jake
jake
2 years ago
Reply to  Pratik Kinage

n=100

i = 1

while (i <= n):
c = 0
if (n % i == 0):
j = 1
while (j <= i):
if (i % j == 0):
c = c + 1
j = j + 1

if (c == 2):
k = n
while (k % i == 0):
k /= i
print(i)

i = i + 1

it stil doesnt work for me

Python Pool
Admin
2 years ago
Reply to  jake

It should work correctly, are you placing the indentations correctly? Also, what error are you facing? Is it related to Syntax Error or Wrong Output?

jake
jake
2 years ago

Is there a way to make a function that take a list of integers and returns a dictionary associating every number with its prime factors.? e.g {18: {2, 3}, 15: {3, 5}}

thanks

Pratik Kinage
Admin
2 years ago
Reply to  jake

Yes, there is. Following code will help you to take a list of integers and return a dictionary with its prime factors –

def prime_factors_list(lst):
  output = {}
  for n in lst:
    factors = []
    for i in range(2,n + 1):
      if n % i == 0:
        count = 1
        for j in range(2,(i//2 + 1)):
          if(i % j == 0):
            count = 0
            break
        if(count == 1):
          factors.append(i)
      output[n]=list(set(factors))
  return output


print(prime_factors_list([18,15, 210, 3, 4, 10]))

Output –

{18: [2, 3], 15: [3, 5], 210: [2, 3, 5, 7], 3: [3], 4: [2], 10: [2, 5]}

Regards,
Pratik

Last edited 2 years ago by Pratik Kinage
jake
jake
2 years ago
Reply to  Pratik Kinage

you are the best
there seem to be a problem with that code tho
the output is
{5: [2, 5], 7: [3, 7], 3: [3, 3]}

Pratik Kinage
Admin
2 years ago
Reply to  jake

Yes, the code was not checking for existing factors earlier. I’ve edited the code in the comment. Let me know if you need any more help.

Regards,
Pratik

jake
jake
2 years ago
Reply to  Pratik Kinage

Thank you, Pratik

strange,still has the same problem of the first(old) code

Pratik Kinage
Admin
2 years ago
Reply to  jake

Sorry, I overlooked the ‘3’ as a factor part. I’ve updated the code again.

Regards,
Pratik

Hesami
Hesami
2 years ago

The result for first method for n=100000000000000001 (16 zeros) is wrong!
The result was 11, 67, 283, 18899, 4
4 is not a prime factor and 11*67*283*18899*4=100000000000000012 which not equal to n

Python Pool
Admin
2 years ago
Reply to  Hesami

I have no idea from where does that 4.0 output comes from. Even the prime factors for this number are wrong. I recommend you use other methods while I debug the issue and fix it.

Python Pool
Admin
2 years ago
Reply to  Hesami

I found the problem. The main problem arises when we divide 100000000000000001 with 11. Here the output should be an odd number but instead, the result is –

>>> 100000000000000001/11
9090909090909092.0

This error is then further extended where we get 4 as a factor. I’ll get to the main reason behind this error and get back to you.

Hesami
Hesami
2 years ago
Reply to  Python Pool

I found the error reason and solved it. If you use n=n//i instead of n=n/i in line 15, the problem will be solved and correct prime factors will comes out.

Python Pool
Admin
2 years ago
Reply to  Hesami

Yes, correct. The division is resulting in incorrect results but the remainder or floor division seems to be working. I found this similar question in Stackoverflow. One of my friends suggested using gmpy2 to handle large numbers in Python. Check it out and let me know if it’s of any use!

Hesami
Hesami
2 years ago
Reply to  Python Pool

I think this is a python bug. The correct result by windows calculator is shown in attached picture. But why the result is correct by floor division!? (//)

Screenshot 2021-11-09 163131.png
Rustem
Rustem
2 years ago

The second method does not work for the numbers 4, 8, 16 …

Pratik Kinage
Admin
2 years ago
Reply to  Rustem

For me, it’s working correctly, can you check it again?

Regards,
Pratik