New update is available. Click here to update.

Last Updated: 2 Jan, 2021

Difficulty: Easy

```
If there is no prime factor of a given integer, then print -1.
```

```
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’.
```

```
For each test case, print the largest prime factor of the given positive integer in a separate line.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

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

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

In the upside-down division or repeated division method of finding prime factorization, we repeatedly divide the number with its smallest factor to find its prime factorization. We can use this method as follows to find the largest prime factor of the given integer.

- 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 sqrt(n) and in each iteration we do the following
- If ‘n’ is divisible by ‘i’ .then update ‘largestFactor’:= i.
- Repeatedly divide ‘n’ by ‘i until ‘n’ is divisible by ‘i’.

- If ‘n’ is greater than 1, then update ‘largestFactor’:= n
- Return ‘largestFactor’.

SIMILAR PROBLEMS

Ninja And The LCM

Posted: 12 Apr, 2022

Difficulty: Easy

A Number Game

Posted: 23 Apr, 2022

Difficulty: Moderate

Pair Product Div by K

Posted: 15 May, 2022

Difficulty: Moderate

Pair Product Div by K

Posted: 15 May, 2022

Difficulty: Moderate

Merge Two Sorted Arrays Without Extra Space

Posted: 19 Nov, 2022

Difficulty: Moderate

Co-Prime

Posted: 14 Dec, 2022

Difficulty: Hard

Popular Interview Problems: