Print all prime factors of a number using Python

Today, we will see a Python program to print all the prime factors of a number. If a number perfectly divides the given number and is a prime number too, then it is a prime factor of that number. In this tutorial, we will get to know what is a prime factor, a method to find prime factors of a number and a Python program which prints all prime factors of a number.

Prime factors of a number

The prime numbers which divide the given number perfectly are known as prime factors of that number. Using the below two conditions we can check whether a number is a prime factor of a given number or not-

  • The number must be a prime number.
  • The number must divide the given number perfectly.

For example-

  • Let us find the prime factors of a number 99.
  • The numbers 1, 3, 9, 11, 33, and 99 are factors of 99. Because these numbers can perfectly divide 99.
  • The numbers 3 and 11 are prime factors of 99. Because these are the prime numbers among factors.
  • So, both the conditions are fulfilled. The numbers 3 and 11 are prime numbers and 99 is perfectly divisible by both the numbers.
  • Finally, we get 3 and 11 as the prime factors of 99.

A method to find prime factors of a given number

To find all the prime factors of a number, we will follow the steps given below-

  1. Store the number in variable ‘num’.
  2. Declare loop control variable ‘i’ and initialize it with 2.
  3. Check whether ‘i’ divides the number perfectly i.e. with no remainder.
  4. If the number is divisible, go to step 5. Otherwise, go to step 8.
  5. Check whether the value in variable ‘i’ is a prime number or not.
  6. If it is prime, print the value.
  7. Otherwise, go to step 8.
  8. Increment the value of ‘i’ by 1.
  9. Go to step 3 and repeat steps until the value of ‘i’ becomes equal to the number.
  10. Stop – all the prime factors of the number are printed.

To understand the above steps in a better way, let us take an example-

num = 6
Iteration 1- value of i = 2
        num % i = 6 % 2 = 0 (True)
        prime = True
        for loop condition is false for first iteration
        So, the number 2 is a prime factor of 6
Iteration 2- value of i = 3
        num % i = 6 % 3 = 0 (True)
        prime = True
        for loop condition is false
        So, the number 3 is a prime factor of 6
Iteration 3- value of i = 4
        num % i = 6 % 4 = 0 (False)
        So, the number 4 is not a prime factor of 6
Iteration 4- value of i = 5
        num % i = 6 % 5 = 0 (False)
        So, the number 5 is not a prime factor of 6
Iteration 5- value of i = 6
        num % i = 6 % 6 = 0 (True)
        prime = True
        Iteration 1- value of j = 2
                6 is divisible by 2
                So, prime = False
        So, the number 6 is not a prime factor of 6

Therefore, numbers 2 and 3 are the prime factors of 6.

Print all prime factors of a number using Python program

Now, we will see a Python program that prints all the prime factors of a given number. Firstly, we will take the number from the user as input and store it in variable ‘num’. Then we check the divisibility of the given number by all numbers from 2 to ‘num’. If the number is divisible, then we check whether the divisor is a prime number. And finally, if it is a prime number, we display it as it is a prime factor of ‘num’. The Python program is as follows-

num = int(input("ENTER A NUMBER : "))
for i in range(2,num + 1):
    if(num % i == 0):
        prime = True
        for j in range(2,(i//2 + 1)):
            if(i % j == 0):
                prime = False
                break
        if(prime):
            print("%d"%i,end=' ')
print("ARE THE PRIME FACTORS OF NUMBER",num)

Python program output

The above Python program prints all the prime factors of a number. The output of this program after sample execution is given below-

[email protected]:~/python$ python3 factors.py
ENTER A NUMBER : 35
5 7 ARE THE PRIME FACTORS OF NUMBER 35
[email protected]:~/python$

So, 5 and 7 are the prime factors of 35.

Thank you for reading this tutorial and I hope it helps you.

Also, read: Check given number is prime or not in Python

Leave a Reply

Your email address will not be published. Required fields are marked *