Largest prime factor

Largest prime factor (Project Euler Problem 3) solution in python . We will discuss all the problems in Project Euler and try to solve them using Python. I have solved Project Euler Problem 2 Even Fibonnaci Numbers in Python as well.

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

What is the largest prime factor of the number 600851475143 ?

So we have to solve this problem using Python.

I am assuming you have already installed Python 2.7.x. If not, you can download it from here.

Lets first of all open Python IDLE.

If we analyze the problem statement given here, we can see that we are asked to calculate the largest prime factor of the given number.

Let’s say we call our number as x

We need to find the largest prime factor of x.

Largest prime factor solution

We need to start from 2 and keep on checking on different numbers and see it divides the given number fully or not.

If it divide it fully we start again from 2 otherwise we keep on checking by adding one to divisor. At the end we will have the largest factor.

def largest_prime_factor(num, div=2):
    while div < num:
        if num % div == 0 and num/div > 1:
            num = num /div
            div = 2
            div = div + 1
    return num

Now lets display the number. It show that 6857 is the largest prime factor of x.

Lets check by entering 6857 as answer in project euler website and see if we got it right.

largest prime factor
Project Euler Problem 3 Solution

Yaay! We got this right. Thanks for reading.

Here is the Problem 4 Solution.

Happy coding!


I am a Software Engineer with ample experience in making games, websites, mobile apps and augmented reality solutions.

Pin It on Pinterest