# Largest prime factor of a number (Project Euler Problem 3)

Sign up for FREE 1 month of Kindle and read all our books for free.

Get FREE domain for 1st year and build your brand new site

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
```