Project Euler Problem 3: Largest prime factor

Problem 3 introduces us to prime numbers. It asks us to find the largest prime factor of the number 600851475143. First we need an is_prime function to check if a number is prime. A quick search on the internet gave me this simple function with \(O(\sqrt{n})\) complexity.

from math import sqrt

def is_prime(n):
  for i in range(2, int(sqrt(n)) + 1):
    if (n % i) == 0:
      return False
  return True

Now we can iterate over the numbers from 2 to the half of the provided number, checking if it is a factor and if it is prime.

n = 600851475143

for i in range(2, n // 2):
  if n % i == 0 and is_prime(i):
    print(i)

This will print the prime factors of the number, and the last one will be the largest.

If you are interested, here is the fastest way to check if a number is prime.

You can find all my solutions in my GitHub Repository!.

Previous problem Next problem