Python Programming Examples

Python Program for Find largest prime factor of a number

Given a positive integer \’n\'( 1 <= n <= 10¹⁵). Find the largest prime factor of a number.

Input: 6
Output: 3
Explanation
Prime factor of 6 are- 2, 3
Largest of them is \'3\'

Input: 15
Output: 5

Python3

Python3

# Python3 code to find largest prime 
# factor of number 
import math 
 
# A function to find largest prime factor 
def maxPrimeFactors (n): 
     
    # Initialize the maximum prime factor 
    # variable with the lowest one 
    maxPrime = -1
     
    # Print the number of 2s that divide n 
    while n % 2 == 0: 
        maxPrime = 2
        n >>= 1     # equivalent to n /= 2 
         
    # n must be odd at this point,  
    # thus skip the even numbers and  
    # iterate only for odd integers 
    for i in range(3, int(math.sqrt(n)) + 1, 2): 
        while n % i == 0: 
            maxPrime = i 
            n = n / i 
     
    # This condition is to handle the  
    # case when n is a prime number  
    # greater than 2 
    if n > 2: 
        maxPrime = n 
     
    return int(maxPrime) 
 
# Driver code to test above function 
n = 15
print(maxPrimeFactors(n)) 
 
n = 25698751364526
print(maxPrimeFactors(n)) 
 
# 

Output:

5
328513

Time complexity: $\text{O}(\sqrt{n})$
Auxiliary space: $\text{O}(1)$

by python-tutorials.in
on 6th October 2019

0

Leave a Reply Cancel reply