Project Euler 3: Largest prime factor - Project Euler Detailed Solutions

Problem

The prime factors of 13195 are 5, 7, 13, and 29.

What is the largest prime factor of the number 600851475143 ?

Solution Approach

In this problem, we are supposed to find the largest prime number which divides the given number.

We will use a basic mathematics theorem called the “fundamental theorem of arithmetic“. It states that every integer which is greater than 1 (i.e n>1) will have unique factorization as a product of prime numbers. It states that every number can be factored down into a set of prime numbers which may not be unique. To give an example 15 can be factored to give 3 and 5 which are prime. Likewise, 45 can be factored in to give 3, 3, 5.

Now with the basic understanding of the theorem, we move on to how it relates to the problem at hand. So if we take a number and divide it repeatedly by its smallest factor (does not matter if it is prime or not), then the last factor must be the largest factor of the given number. That is what we are going to do in this problem. We will find the smallest factor, divide the number by this factor. After that, update the number with the quotient which we get after the division. This process will continue until the number cannot be divided further, hence we get the largest prime factor of the given number.

The time complexity of this approach is O(nlog n) as we have to find the smallest factor periodically (to divide) and then the number decreases logarithmically after dividing the number with the factor obtained. This process continues till we get the largest prime factor. The space complexity is O(1) as we are not using any extra space in this problem.

Code Breakdown

Coming to the code part of the problem, we will first initialize the n which is user-defined. Then we run an infinite loop where we calculate the smallest prime factor of the number. We can make a helper function to modularize the work.

The helper function is to get the lowest factor. In that, we just run a loop from 2 to the square root of the number. It will check if the number is divisible by the looping variable. If that is the case then we return that looping variable as a factor in our main function. If the loop runs to the conclusion then we return the number itself as it is prime.

Coming back to the main function, after getting the smallest factor we just check if it is less than number n and if it is then we divide by the same factor. If not then we return the same as the answer.

Solution Code

Python Solution

import math

def calculate_largest_prime_factor():
	n = 600851475143
	while True:
		smallest_factor = smallest_prime_factor(n)
		if smallest_factor < n:
			n //= smallest_factor
		else:
			return smallest_factor


def smallest_prime_factor(n):
	end = int(math.sqrt(n))
	for i in range(2, end + 1):
		if n % i == 0:
			return i
	return n  

print(calculate_largest_prime_factor())

import math

def calculate_largest_prime_factor():

n = 600851475143

while True:

smallest_factor = smallest_prime_factor(n)

if smallest_factor < n:

n //= smallest_factor

else:

return smallest_factor

def smallest_prime_factor(n):

end = int(math.sqrt(n))

for i in range(2, end + 1):

if n % i == 0:

return i

return n

print(calculate_largest_prime_factor())

Java Solution

import java.lang.Math;

class Solution{
  public static void main(String[] args) {			
		long n = 600851475143L;
		while (true) {
			long smallestFactor = smallestPrimeFactor(n);
			if (smallestFactor < n)
				n /= smallestFactor;
			else{
				System.out.println(smallestFactor);
				return;
			}		
		}
	}
	
	private static long smallestPrimeFactor(long n) {
		long end = (long) Math.sqrt((double) n);
		for (long i = 2; i <= end; i++) {
			if (n % i == 0)
				return i;
		}
		return n;
	}
}

import java.lang.Math;

class Solution{

public static void main(String[] args) {

long n = 600851475143L;

while (true) {

long smallestFactor = smallestPrimeFactor(n);

if (smallestFactor < n)

n /= smallestFactor;

else{

System.out.println(smallestFactor);

return;

}

private static long smallestPrimeFactor(long n) {

long end = (long) Math.sqrt((double) n);

for (long i = 2; i <= end; i++) {

if (n % i == 0)

return i;

}

return n;

}

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding 🙂