Python Program To Find Largest Prime Factor of a Number

In this article, we will have a hands-on experience to find the largest prime factor of a number with help of Python Programming by two different approaches.

Prime Factorization - Basic Introduction

Prime factorization using the factor tree method, and prime factorization using the division method.

• Prime Factorization using factor-tree method: The factor tree approach involves finding a number's factors and then factorizing those numbers until we reach prime numbers. Follow the steps below to determine a number's prime factorization using the factor tree approach.
  1. Consider the number to be the root of the factor tree's topmost branch.
  2. Then, as the tree's branches, write down the relevant pair of factors.
  3. Factorize the composite factors discovered in step 2 and record the pair of factors like the tree's next branches.
  4. Repeating the 3rd step, unless we get all the factors.
• Division Method: By dividing a huge integer by prime numbers, the division method can be used to identify the prime factors. To find the prime factors of an integer using the division method, follow the steps below:
  1. Dividing the number by the smallest prime number in such a way that the smallest prime number entirely divides the number.
  2. Divide step 1's quotient by the smallest prime number once again.
  3. Repeating unless and until quotient results out to 1.
  4. At last, multiply all of the divisors of the division by all of the prime factors.

Largest Prime Factor - Concept

The concept of the largest prime factor is very straightforward. Let's break it down:

• Every number is influenced by a variety of factors.
• Factors are numbers that divide a given number entirely to leave zero as a residue.
• Let us have a look at an example: When we look at the number 6, we can see that it has four factors: 1,2,3,6. Two and three, on the other hand, are prime numbers. 3 is the highest prime factor of number 6 because it is greater than 2.

We are now ready to dive deep into the programming version of finding the largest prime factor of a number.

Python Approach to find a largest prime factor of a number

To find the largest prime factor of a number we will go with two different approaches. The first approach is by taking input from the user and the second approach is by pre-inputting out the number in the code itself. Let us first see the algorithmic approach of the program:

Algorithm:

1. In the first step, we have to factorize the given number input by dividing it by the divisor of a number.
2. Now, we have to check the number by comparing them and result out the highest number.

Code Snippets

Python Progarm to Find Largest Prime Factor by taking User Input

import math

# input from user 
a = int(input("Enter the number : "))

maxPrime = 0
# converting the number to odd
while a % 2 == 0:
	maxPrime = 2
	a = a/2	

# prime factors and replacing maxPrimeFactor
for i in range(3, int(math.sqrt(a)) + 1, 2):
	while a % i == 0:
		maxPrime = i
		a = a / i
if a > 2:
	maxPrime = a
		
print("The largest prime Factor of number is ",int(maxPrime))
  

Enter the number: 60
The largest prime Factor of number is 5

Python Program to find Largest Prime Factor by pre-inputted number

def isPrime(a):
    # invalid input
    if a <= 1:
        return False

    #  potential divisors
    for i in range(2,a):
        if a % i == 0:
            return False 
      

    # no divisor found, it's a prime number
    return True
# pre-inputted
number = 60

# a list to store prime factors of a number
Prime_F=[]
Prime_F.append(1)

for i in range(2, number//2 + 1):
    # if number is a factor
    if number % i == 0:
        # if factor is also a prime
        if isPrime(i)==True:
            # add number to the list
           Prime_F.append(i)
# output 
print("The Largest Prime Factor of given number is  =",max(Prime_F))

The largest Prime Factor of a given number is = 5

Code Description:

Before we can calculate a number, we must first determine all of the variables that influence it. When we consider the number 60, for example, we can see that it is made up of three factors: 2,3,5. A loop from 2 to half the number is run in the code. The loop will be from 2 to 7 in this instance. Now we'll see if each factor is a prime number as well. We have a helper function in the code that checks whether an integer is prime or not — we call it on every factor. We add the number to the preserved list of factors if it is both a factor and a prime. Finally, we take the highest number from the list to get the largest prime factor.

Conclusion

In this tutorial, we have seen what is prime factorization, How to calculate the largest prime factor of a number, and two different approaches to find out the largest prime factor of a number. The first approach is by taking user input and the second approach is by pre-inputted numbers in the code itself.