ADVERTISEMENT
ADVERTISEMENT

Python program to find the largest prime factor of a number

Here, we will take an input from the user and return the largest possible prime factor of the given number.
Submitted by Shivang Yadav, on April 12, 2021

Python programming language is a high-level and object-oriented programming language. Python is an easy to learn, powerful high-level programming language. It has a simple but effective approach to object-oriented programming.

Prime factor of a number is the factors of the number which is prime.

Finding the largest prime factor of a number

We will take an integer as input from the user and then find the largest prime factor of the number.

Example:

Input:
N = 21

Output:
7

Prime factors of 21 = 3, 7. 
Largest of them is 7.

We will find all the prime factors of the number and then return the largest of all.

To find the maximum prime factor we will first check if the number is divisible by 2, i.e. even. If yes, make it odd and initialize the maxPrimeFactor = 2.

Then, for each number from 3, find all the divisors of the number (first will be prime) -> initialize maxPrimeFactor with the divisor. And divide the number by it until it no longer is divisible by the number. Doing this will make sure any multiple of this prime number will not be able to divide the number.

At the end print the maxPrimeFactor.

Program to find the largest prime factor of a number

# Python program to find the 
# largest prime factor of a number

import math

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

maxPrimeFactor = 0
# Checking and converting the number to odd
while n % 2 == 0:
	maxPrimeFactor = 2
	n = n/2	

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

Output:

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

Python Basic Programs »



ADVERTISEMENT



ADVERTISEMENT



Comments and Discussions


ADVERTISEMENT

ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.