EULER CODE - 3

QUESTION - 

The prime factors of 13195 are 5,7,13 and 29.

What is the largest prime factor of a given number N?

Input Format

First-line contains T, the number of test cases. This is followed by T lines each containing an integer N.

Constraints

• 1 ≤ T ≤ 10
• 10 ≤ N ≤ 10¹²

Output Format

For each test case, display the largest prime factor of N.

Sample Input 

2

10

17 

Sample Output

5

17

Ans : 

This question has a very simple logic to solve it, finding the last prime number which divides the number by increasing the value of the variable that stores the examining prime number.

C++ Approach :-

#include<bits/stdc++.h>

using namespace std;

int main()

{

    int t;

    cin >> t;

    while(t--)

    {

        long long int n;

        cin >> n;

        long long div = 2;

        while(div<=floor(sqrt(n)))  /// checking till square-root to have the optimization

        {

            if(n%div==0)

            {

                n/=div;

            }

            else

            {

                div++;

            }

        }

        cout << n << endl;

    }

    return 0;

}

Python Approach:-

import math

t = int(input())

for i in range(t):

    n = int(input())

    div = 2

    while(div <= math.floor(math.sqrt(n))):

        if(n%div==0):

            n = n//div

        else:

            div = div+1

    print(n)

Hope that helps, keep coding :)