Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 30 minutes | Coding time: 5 minutes
In this problem, we need to find the largest prime factor of a given number N. We will bring in some insights and solve this in O(√N loglog N) time complexity. There are multiple approaches to solve this problem like:
- Generate all prime numbers using sieve techniques O(N log log N)
- Use our insights to improve above approach O(√N log log N)
In summary, the key ideas are (which we have explained further):
- (Idea 1) There can atmost one prime factor of N that is greater than √N
- (Idea 2) Once you find a prime factor say P, you can reduce the original number by N/P.
- (Idea 3) If after dividing N by all factors < √N, it is greater than 1 then, the remaining number is a prime number (as per Idea 1) and is the largest prime factor as well.
With this, you will be able to solve the Problem 3 of Project Euler.
With our algorithm, we are able to improve by a factor of √N which is significant.
Basic approach O(N log log N)
The key idea in this approach is to generate all prime numbers that are less than N and get the largest prime number in this list. To generate prime numbers in this case, we can use any of the popular sieve techniques are are fast and efficient as well. They are:
Such algorithm takes O(N * (log log N)) time to compute all prime numbers less than N.
The simplest is Sieve of Eratosthenes where the idea is to eliminate all multiples of prime numbers. It starts with 2 and takes the next available number as its starting point.
Note that we can assume that there are N / logN number of primes less than N.
Hence, once you have the list of primes numbers less than N, you need to divide N by each of the prime numbers and get the largest prime number that divides it.
The pseudocode of this approach is:
// O(N loglog N)
list[] = Generate all prime numbers < N (any sieve technique)
// O(N / log N)
for(i = length(list)-1; i >= 0; i--)
if(N % i == 0)
return i;
The main part of the implementation is the largest_factor() function which you should observe carefully as we will be optimizing this section of code greatly.
static int largest_factor(int N)
{
checkPrime = new boolean [N+1];
sieve(N); // generates all primes less than N
int count = 2, largest = 0;
while (count <= N)
{
if(checkPrime[count] == true && N % count == 0)
largest = count;
count ++;
}
return largest;
}
Implementation:
import java.util.Scanner;
public class opengenus
{
static boolean checkPrime[];
static void sieve (int n)
{
int a=2;
for(int i=0; i<n; i++)
{
checkPrime[i] = true;
}
for(int i=a ; i*i<=n ; i++)
{
if(checkPrime[i] == true)
{
for(int j=i*2 ; j<=n ; j=j+i)
{
checkPrime[j] = false;
}
}
}
}
static int largest_factor(int N)
{
checkPrime = new boolean [N+1];
sieve(N);
int count = 2, largest = 0;
while (count <= N)
{
if(checkPrime[count] == true && N % count == 0)
largest = count;
count ++;
}
return largest;
}
public static void main(String [] args){
int N = 9987;
int answer = largest_factor(N);
System.out.println(answer);
}
}
Output:
3329
The time complexity of this approach is O(N loglog N)
We will improve this greatly.
Efficient approach
To improve the above approach, we will gain some insights to significantly optimize the above approach. Key ideas:
- (Idea 1) There can atmost one prime factor of N that is greater than √N
- (Idea 2) Once you find a prime factor say P, you can reduce the original number by N/P.
- (Idea 3) If after dividing N by all factors < √N, it is greater than 1 then, the remaining number is a prime number (as per Idea 1) and is the largest prime factor as well.
Due to the above insights, we just need to generate prime numbers upto √N for the worst case. Apart from this, the other parts remain the same with some small changes.
Let us analyze why the insights hold true?
If N is not a prime number, then it will have atleast 2 factors say N1 and N2.
So, in this case, N1 * N2 = N. If N1 = N2, then both are equal to √N. If this is not the case, then one has to be less than √N, as both cannot be greater than √N.
Suppose N1 > √N and N2 > √N which implies N1 * N2 > N which is not possible.
Hence, there can be atmost one factor which is greater than √N. So, if you have found all factor less than √N and divide N by all the factors, the remaining number is a prime number and is the largest prime factor.
With this, you can solve this problem efficiently.
Pseudocode:
// Idea 1
// O(√N loglog N)
list[] = Generate all prime numbers < √N (any sieve technique)
// O(√N / log N)
for(i in list)
{
if(N % i == 0)
{
// Idea 2
N = N / i;
largest = i;
}
}
// Idea 3
if N > 1
return N;
return largest;
The main focus is the largest factor function which is as follows:
static int largest_factor(int N)
{
// Idea 1
int limit = (int)Math.ceil(Math.sqrt((double)N));
checkPrime = new boolean [limit+1];
sieve(limit);
int count = 2, largest = 0;
while (count <= limit)
{
if(checkPrime[count] == true && N % count == 0)
{
largest = count;
// Idea 2
N = N / count;
}
count ++;
}
// Idea 3
if (N > 1)
return N;
return largest;
}
Implementation:
import java.util.*;
public class opengenus
{
static boolean checkPrime[];
static void sieve (int n)
{
int a=2;
for(int i=0; i<n; i++)
{
checkPrime[i] = true;
}
for(int i=a ; i*i<=n ; i++)
{
if(checkPrime[i] == true)
{
for(int j=i*2 ; j<=n ; j=j+i)
{
checkPrime[j] = false;
}
}
}
}
static int largest_factor(int N)
{
int limit = (int)Math.ceil(Math.sqrt((double)N));
checkPrime = new boolean [limit+1];
sieve(limit);
int count = 2, largest = 0;
while (count <= limit)
{
if(checkPrime[count] == true && N % count == 0)
{
largest = count;
N = N / count;
}
count ++;
}
if (N > 1)
return N;
return largest;
}
public static void main(String [] args){
int N = 9987;
int answer = largest_factor(N);
System.out.println(answer);
}
}
Output:
3329
