# 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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The approach is simple, just factorise the given number by dividing it with the divisor of a number and keep updating the maximum prime factor. See this to understand more.

## C++

 `// C++ Program to find largest prime ` `// factor of number ` `#include ` `#include ` `using` `namespace` `std; ` ` `  `// A function to find largest prime factor ` `long` `long` `maxPrimeFactors(``long` `long` `n) ` `{ ` `    ``// Initialize the maximum prime factor ` `    ``// variable with the lowest one ` `    ``long` `long` `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` `(``int` `i = 3; i <= ``sqrt``(n); i += 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` `maxPrime; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``long` `long` `n = 15; ` `    ``cout << maxPrimeFactors(n) << endl; ` ` `  `    ``n = 25698751364526; ` `    ``cout <<  maxPrimeFactors(n); ` ` `  `} ` `// This code is contributed by Shivi_Aggarwal `

## C

 `// C Program to find largest prime ` `// factor of number ` `#include ` `#include ` ` `  `// A function to find largest prime factor ` `long` `long` `maxPrimeFactors(``long` `long` `n) ` `{ ` `    ``// Initialize the maximum prime factor ` `    ``// variable with the lowest one ` `    ``long` `long` `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` `(``int` `i = 3; i <= ``sqrt``(n); i += 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` `maxPrime; ` `} ` ` `  `// Driver program to test above function ` `int` `main() ` `{ ` `    ``long` `long` `n = 15; ` `    ``printf``(````"%lld "````, maxPrimeFactors(n)); ` ` `  `    ``n = 25698751364526; ` `    ``printf``(``"%lld"``, maxPrimeFactors(n)); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java Program to find largest ` `// prime factor of number ` `import` `java.io.*; ` `import` `java.util.*; ` ` `  `class` `GFG { ` ` `  `    ``// function to find largest prime factor ` `    ``static` `long` `maxPrimeFactors(``long` `n) ` `    ``{ ` `        ``// Initialize the maximum prime ` `        ``// factor variable with the ` `        ``// lowest one ` `        ``long` `maxPrime = -``1``; ` ` `  `        ``// Print the number of 2s ` `        ``// that divide n ` `        ``while` `(n % ``2` `== ``0``) { ` `            ``maxPrime = ``2``; ` ` `  `            ``// equivalent to n /= 2 ` `            ``n >>= ``1``; ` `        ``} ` ` `  `        ``// n must be odd at this point, ` `        ``// thus skip the even numbers ` `        ``// and iterate only for odd ` `        ``// integers ` `        ``for` `(``int` `i = ``3``; i <= Math.sqrt(n); i += ``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` `maxPrime; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `main(String[] args) ` `    ``{ ` `        ``Long n = 15l; ` `        ``System.out.println(maxPrimeFactors(n)); ` ` `  `        ``n = 25698751364526l; ` `        ``System.out.println(maxPrimeFactors(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by Gitanjali `

## 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)) ` ` `  `# This code is contributed by "Sharad_Bhardwaj". `

## C#

 `// C# program to find largest ` `// prime factor of number ` `using` `System; ` ` `  `class` `GFG { ` ` `  `    ``// function to find largest prime factor ` `    ``static` `long` `maxPrimeFactors(``long` `n) ` `    ``{ ` `        ``// Initialize the maximum prime ` `        ``// factor variable with the ` `        ``// lowest one ` `        ``long` `maxPrime = -1; ` ` `  `        ``// Print the number of 2s ` `        ``// that divide n ` `        ``while` `(n % 2 == 0) { ` `            ``maxPrime = 2; ` ` `  `            ``// equivalent to n /= 2 ` `            ``n >>= 1; ` `        ``} ` ` `  `        ``// n must be odd at this point, ` `        ``// thus skip the even numbers ` `        ``// and iterate only for odd ` `        ``// integers ` `        ``for` `(``int` `i = 3; i <= Math.Sqrt(n); i += 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` `maxPrime; ` `    ``} ` ` `  `    ``// Driver code ` `    ``public` `static` `void` `Main() ` `    ``{ ` `        ``long` `n = 15L; ` `        ``Console.WriteLine(maxPrimeFactors(n)); ` ` `  `        ``n = 25698751364526L; ` `        ``Console.WriteLine(maxPrimeFactors(n)); ` `    ``} ` `} ` ` `  `// This code is contributed by vt_m `

## PHP

 `>= 1;  ` `    ``} ` ` `  `    ``// n must be odd at  ` `    ``// this point, thus skip ` `    ``// the even numbers  ` `    ``// and iterate only for ` `    ``// odd integers ` `    ``for` `(``\$i` `= 3; ``\$i` `<= sqrt(``\$n``); ``\$i` `+= 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` `\$maxPrime``; ` `} ` ` `  `    ``// Driver Code ` `    ``\$n` `= 15; ` `    ``echo` `maxPrimeFactors(``\$n``), ````" "````; ` ` `  `    ``\$n` `= 25698751364526; ` `    ``echo` `maxPrimeFactors(``\$n``), ````" "````; ` ` `  `// This code is contributed by aj_36 ` `?> `

Output:

```5
328513
```

Time complexity:
Auxiliary space: