Python Prime factorization

Python Prime factorization

In this tutorial, we will design a program where we will find all the prime factors of a number. Then, we will print all these prime factors of the given number in the output of the number.

A Python program to find all the prime factors of any number

Before proceeding with the Python program, look at the following example:

• Prime factor of 105: 3, 5, 7
• Prime factor of 246: 2, 3, 41 etc.

Following are the key steps for program:

1). When the given number is divisible by 2, we should print 2 in output and divide the number by 2. We have to follow this step until the number is no more divisible by 2.

2). After completing the step 1, the given number is now must be odd. Now, we have to start for loop on the resultant number from step 1, from i = 3 to square root of the given number. Print i integer in output everytime when i divides the resultant number.

3). When number is not divisible by i, print the remaining resultant number in the output.

This will be the prime factors of a given number in the program.

Note

We also have to add a condition where the number given by user maybe a prime number in itself. So, for this case we have to write if condition statement in the program where the given number should be greater than 1.

Now, look at the following program to find all the prime factors of a number and after running the following program we will understand it's working and functioning in detail:

Example –

 # Importing math module in Python
 import math
 # Design a function PrimeFactorization for prime factors of number
 def PrimeFactorization(a):
 # Use the while loop for checking divisibility by 2
             while a % 2 == 0:
                         print (2), # printing 2 until condition become false
                         a = a / 2
             # Using a for loop withsqrt() function of math module  
             for b in range(3,int(math.sqrt(a))+1,2):
 # Using a while loop inside for loop
                         while a % b == 0:
                                     print (b), # printing all odd prime factors
                                     a = a / b
             # Using the if condition
             if a > 2:
                         print (a) # if condition satisfies it will print original number
 # Take a positive prime number from user
 a = int(input("Enter a positive integer number: "))
 # Print all prime factors of given number
 print("The prime factors are : ")
 PrimeFactorization(a) # calling out PrimeFactorization function 

Output:

 Enter a positive integer number: 25515
 The prime factors are:
 3
 3
 3
 3
 3
 3
 5
 7 

Working of the program:

Now, let's understand how the program works so that we know how with this program Python finding the prime factors of any given number.

• We designed a PrimeFactorization function, where we perform operations on number given by user.
• First, we used a while loop to follow the step 1, and divided the number by 2 until the condition 'a % 2 = 0' becomes false. We printed the 2 in output everytime while loop runs i.e., print(a).
• When the condition becomes false, it means we know that now the resultant number is odd.
• Now, we used for loop in the second step and assigned a = b. Then, we used the while loop to follow the condition, from b = 3 to square root of a. It will print all the odd prime factors of number a with print(b) statement.
• After that, we have also used to if statement condition to check the condition that given number by user is greater than 1.
• Then, we defined variable a and store the number in it that user will provide while running the program.
• After that, we called out the PrimeFactorization function and provided argument 'a' in the function. It will print all the prime factors of number in the output when we run the program.