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.
- Consider the number to be the root of the factor tree's topmost branch.
- Then, as the tree's branches, write down the relevant pair of factors.
- Factorize the composite factors discovered in step 2 and record the pair of factors like the tree's next branches.
- 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:
- Dividing the number by the smallest prime number in such a way that the smallest prime number entirely divides the number.
- Divide step 1's quotient by the smallest prime number once again.
- Repeating unless and until quotient results out to 1.
- 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:
- In the first step, we have to factorize the given number input by dividing it by the divisor of a number.
- Now, we have to check the number by comparing them and result out the highest number.
Python Progarm to Find Largest Prime Factor by taking User Input
# 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
# invalid input
if a <= 1:
# potential divisors
for i in range(2,a):
if a % i == 0:
# no divisor found, it's a prime number
number = 60
# a list to store prime factors of a number
for i in range(2, number//2 + 1):
# if number is a factor
if number % i == 0:
# if factor is also a prime
# add number to the list
print("The Largest Prime Factor of given number is =",max(Prime_F))
The largest Prime Factor of a given number is = 5
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.
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.