# Largest Prime Factor

Posted: 2 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

#### You are given a positive integer ‘n’. Your task is to find the largest prime factor of this given positive integer.

##### Note :
``````If there is no prime factor of a given integer, then print -1.
``````
##### Input Format :
``````The first line of input contains an integer ‘T’ denoting the number of test cases.

The first and only line of each test case contains a positive integer ‘n’.
``````
##### Output Format :
``````For each test case, print the largest prime factor of the given positive integer in a separate line.
``````
##### Note :
``````You do not need to print anything, it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 50
1 <= n <= 10^9

Where ‘T’ is the number of test cases and ‘n’ is the size of the array.

Time Limit: 1 sec
`````` Approach 1
• If the given integer is 1, then return -1 as there is no prime factor of 1.
• Initialize a variable ‘largestFactor’:= 0, it will store the largest prime factor of the given number.
• Run a loop where ‘i’ ranges from 2 to n and for each ‘i’ check whether it is the prime factor of ‘n’ or not. This can be done as follows.
• If n is not divisible by ‘i’ then ‘i’ cannot be the prime factor, otherwise, we need to check whether ‘i’ is prime or not.
• Run a loop where ‘j’ ranges from 2 to square root of ‘i’ if for any ‘j’, ‘i’ is divisible by ‘j’ then it cannot be a prime number.
• If ‘i is prime and ‘n’ is divisible by ‘i’, then update ‘largestFactor’:= i.
• Return ‘largestFactor’.