## Friday, November 25, 2016

### Largest Prime Factor

The prime factors of  are  and .
What is the largest prime factor of a given number ?
Input Format
First line contains , the number of test cases. This is followed by  lines each containing an integer .
Constraints
Output Format
For each test case, display the largest prime factor of .
Sample Input 0
2
10
17

Sample Output 0
5
17

Explanation 0
• Prime factors of  are , largest is .
• Prime factor of  is  itself, hence largest is .

*************************
PROGRAM
*************************

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int checkPrime(long long n)
{
long long sq=sqrt(n),i;
long long pr[16] ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
if(n%2==0)
return 0;
i=0;
for(;i<16&&n>pr[i];)
{
if(n%pr[i]==0)
return 0;
i++;
}
for(i=10;6*i<=sq;i++)
{
if(n%(6*i-1)==0 || n%(6*i+1)==0  )
return 0;
}
return 1;
}
int main(){
int t;
scanf("%d",&t);
for(int a0 = 0; a0 < t; a0++){
long long n,sq,prime,j;
scanf("%lld",&n);
if(checkPrime(n)==1)
prime=n;
else
{
sq=n/2;
if(sq%2==0)
sq=sq+1;
for(j=sq;j>=3;j=j-2)
{
if(n%j==0)
{
if(checkPrime(j)==1)
{
prime=j;
break;
}
}
}
}
printf("%lld\n",prime);
}
return 0;
}