Largest Prime Factor

Posted: 2 Jan, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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’.
Try Problem