Largest Prime Factor

Easy
0/40
Average time to solve is 15m
profile
Contributed by
15 upvotes
Asked in companies
IntuitBarclaysPolicyBazaar.com

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
5 
27
Sample Output 1 :
5
3
Explanation of the Sample Input1 :
Test case 1:
5 is a prime number, so its largest prime is 5 itself  

Test case 2:
Prime factorization of 27 is 3*3*3.
Thus, it's an only prime factor is 3.
Sample Input 2 :
2
14
30
Sample Output 2 :
7
5
Explanation of the Sample Input 2 :
Test case 1 :
Prime factorization of 14 is 2*7.
It has two prime factors, 2 and 7, the largest prime number out of them is 7.

Test case 2 :
Prime factorization of 30 is 2*3*5.
It has three prime factors, 2, 3, and 5, the largest of them is 5.
Hint

One by one check for all positive integers between 2 and ‘n’ (inclusive).

Approaches (2)
Brute Force
  • 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’.
Time Complexity

O(n*sqrt(n)), where ‘n’ is the given positive integer.

 

In the worst case, it takes sqrt(n) time to check whether the given number is prime or not. Here, in the worst case, we have to check for ‘n’ integers whether they are prime or not, which makes its complexity O(n*sqrt(n)).

Space Complexity

 O(1)

 

We are not using any extra space here.

Code Solution
(100% EXP penalty)
Largest Prime Factor
Full screen
Console