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 .
NOTE: WRITE YOUR CODE IN COMMENTS SECTION






*************************
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;
}

Contact Geek Placement Preparation

Name

Email *

Message *