HACKER RANK Project Euler 03 - Largest Prime Factor - Solution.'C++'

Project Euler Challenges-03 - Largest Prime Factor Solution
Problem Statement
This problem is a programming version of Problem 3 from projecteuler.net
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.
Output Format
For each test case, display the largest prime factor of N.
Constraints
1T10
10N1012
Sample Input
2
10
17
Sample Output
5
17

Solution:


#include <iostream>
    #include <cmath>
    #include <vector>
    using namespace std;
    bool checkPrime(long long x)
    {
    for(long long i=2;i<=ceil(sqrt((double)x));++i)
    if(x%i==0)
    return false;
    return true;
    }
    const int N=1000008;
    bool mark[N+100];
    int main()
    {
    for(int i=2;i<=N/2;++i)
    {
    if(mark[i]==false)
    {
    int b=i+i;
    while(b<=N)
    {
    mark[b]=true;
    b+=i;
    }
    }
    }
    vector<int> primes;
    for(int i=2;i<=N;++i)
    if(!mark[i])
    primes.push_back(i);
    int t;
    cin>>t;
    for(int k=1;k<=t;++k)
    {
    long long n;
    cin>>n;
    long long ans=0;
    for(int i=0;i<primes.size();++i)
    {
    if(n%primes[i]==0)
    {
    ans=primes[i];
    while(n%primes[i]==0)
    n/=primes[i];
    }
    }
    if(checkPrime(n) && n>ans)
    ans=n;
     
    cout<<ans<<endl;
    }
    }

Thanks for Visiting, Hope this helps you....



Comments

Popular Posts