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.
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 solveForSieve() {
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);
solveForSieve();
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
One thought on “Sieve of Eratosthenes | HackerRank Solution”