Project Euler Problem 3 - Largest Prime Factor

Project Euler Problem 3 asks us to find the largest prime factor of 600,851,475,143. This problem combines fundamental number theory with straightforward Python implementation to solve what initially seems like an intimidating challenge.

The Approach

My solution breaks down into three key steps:

1. Generate prime numbers up to 1,000,000

2. Identify which primes are factors of our target number

3. Return the maximum from those factors

The Implementation

The solution starts with a prime detection function using trial division. The function checks divisibility from 2 up to the square root of the candidate number—this works because if n has a divisor greater than √n, it must also have a corresponding divisor less than √n.

Next, I generate all primes up to 1,000,000 by testing each number with our is_prime() function. With this prime list ready, we test each prime to see if it divides our target number evenly, collecting all prime factors along the way.

Finally, we return the maximum value from our list of prime factors.

python

import math

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

prime_numbers = []
prime_factors = []

for i in range(0, 1000000):
    if is_prime(i):
        prime_numbers.append(i)

for prime_number in prime_numbers:
    if 600851475143 % prime_number == 0:
        prime_factors.append(prime_number)

print(max(prime_factors))

The Answer

Running this code reveals that the largest prime factor of 600,851,475,143 is 6857.