Largest Prime Factor
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

Question

Largest Prime Factor

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

Accepted Answer

The direct approach is to traverse all elements of the array one by one. Initialise two variables max and second_max. For every element, check whether it is prime or not. If it is prime, update max and second_max accordingly. At the end, return the value stored in second_max variable.

The efficient approach would be to generate all primes upto maximum element of the array using sieve of Eratosthenes and store them in a hash. Now traverse the array and find the second maximum element which is prime using the hash table.
Time Complexity : O(n*log(log(n))

Accepted Answer

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

Space Complexity: O(1)Explanation:

O(1)

We are not using any extra space here.

Time Complexity: OtherExplanation:

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

Accepted Answer

Upside-Down Division

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

Space Complexity: O(1)Explanation:

O(1)

We are using constant space.

Time Complexity: OtherExplanation:

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

The worst-case will occur when ‘n’ is a prime integer, and in the worst case, we do sqrt(n) iteration

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

Note :

Input Format :

Output Format :

Note :

Constraints :

Top Times Internet Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Times Internet Software Developer