Sieve of Eratosthenes | HackerRank Solution

What is the largest prime factor of a given number ?

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^12

Output Format

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

Sample Input 0

2
10
17

Sample Output 0

5
17

Explanation 0

  • Prime factors of 10  are [2, 5] , largest is 5.
  • Prime factor of  17 is 17 itself, hence largest is 17.

Problem Statement:

Largest prime factor

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to any given limit. It is one of the most efficient ways to find all primes smaller than n when n is less than or equal to 10 million.

Sieve of Eratosthenes does so by iteratively marking numbers in the range as composite by marking the multiples of each prime as non-prime. It starts with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime i.e. p*p, p*(p+1), p*(p+2)…….n. We start from p*p, because all the previous composites are already marked as non-prime or composite.

Time complexity of Sieve of Eratosthenes is O(n*log(log(n))).
Here’s a nice explanation:
Time complexity of Sieve of Eratosthenes

Solution

//
//  main.cpp
//  Sieve of Eratosthenes
//
//  Created by Himanshu on 18/08/21.
//
#include <iostream>
#include <cmath>
#include <cstdio>
#include <vector>
using namespace std;
typedef unsigned long long ll;
int sieve[2000000] = {0};

void solve() {
    ll i,j;

    // marking all evens as non-prime
    // if: sieve[i] = 0, it is prime
    // if sieve[i] = 1, it is composite
    for (i=4; i<=1000001; i+=2) {
        sieve[i] = 1;
    }

    // Checking all odd numbers
    for (i=3; i<=1000001; i+=2) {
        for (j=i*i; j<=1000001; j+=i) {
            sieve[j] = 1;
        }
    }
    
}

// Utility function to check if a particular
// number is prime
bool isprime(ll n) {
    ll i,root;
    root = (ll)sqrt(n) + 1;
    
    for (i=2; i<=root; i++) {
        if (n%i == 0) {
            return false;
        }
    }
    
    return true;
}


int main() {
    
    ll T, n, sol, root, tp;
    scanf("%llu",&T);
    
    solve();
    
    while (T--) {
        scanf("%llu",&n);
        root = (ll)sqrt(n) + 1;
        sol = n;
          
        for (ll i=2; i<=root; i++) {
            
            if (n%i == 0) {
                tp = n/i;
                if (sieve[i] == 0) {
                  sol = i;
                }
                  
                // selecting the larger prime between tp and i
                if (tp > i) {
                    if (tp <= 1000000) {
                        if (sieve[tp] == 0) {
                            sol = tp;
                            break;
                        }
                    } else if (isprime(tp)) {
                        sol = tp;
                        break;
                    }
                }
            }
        }

        printf("%llu\n",sol);
    }

    return 0;
}

Here’s a working example:
Ideone

Leave a Reply

Your email address will not be published.