# Python Program for Find largest prime factor of a number

Given a positive integer \’n\'( 1 <= n <= 1015). 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 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 = 15print(maxPrimeFactors(n))  n = 25698751364526print(maxPrimeFactors(n))  #

Output:

5
328513


Time complexity:
Auxiliary space: