Problem Statement

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

What is the largest prime factor of the number 600851475143?

Understanding the Problem

We need to:

  1. Find all prime factors of $600,851,475,143$
  2. Return the largest one

For example, with 13195:

My Solution (Using primePy Library)

1
2
3

from primePy import primes

max(primes.factors(600_851_475_143))

Result: 6857

How This Solution Works

The primePy library provides optimized functions for prime number operations:

Note: Make sure to install primePy first:

1

pip install primePy

Alternative Solutions (No External Libraries)

Solution 1: Basic Trial Division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def largest_prime_factor_basic(n):
    """Find largest prime factor using basic trial division."""
    largest = 1
    
    # Handle factor 2
    while n % 2 == 0:
        largest = 2
        n //= 2
    
    # Check odd factors from 3 onwards
    factor = 3
    while factor * factor <= n:
        while n % factor == 0:
            largest = factor
            n //= factor
        factor += 2
    
    # If n is still > 1, then it's a prime
    if n > 1:
        largest = n
    
    return largest

Solution 2: Optimized Trial Division

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def largest_prime_factor_optimized(n):
    """Optimized version with square root limit."""
    def is_prime(num):
        if num < 2:
            return False
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True
    
    largest = 1
    
    # Start from 2 and go up to sqrt(n)
    for i in range(2, int(n**0.5) + 1):
        while n % i == 0:
            largest = i
            n //= i
    
    # If n is still > 1, it's a prime factor
    if n > 1:
        largest = n
    
    return largest

Solution 3: More Efficient Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def largest_prime_factor_efficient(n):
    """Most efficient pure Python approach."""
    largest = 1
    
    # Remove factor 2
    if n % 2 == 0:
        largest = 2
        while n % 2 == 0:
            n //= 2
    
    # Check odd numbers from 3
    i = 3
    while i * i <= n:
        if n % i == 0:
            largest = i
            while n % i == 0:
                n //= i
        i += 2
    
    # If n is still > 1, it's the largest prime factor
    if n > 1:
        largest = n
        
    return largest

Solution 4: Generator-Based Approach

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

def prime_factors_generator(n):
    """Generate all prime factors of n."""
    # Handle factor 2
    while n % 2 == 0:
        yield 2
        n //= 2
    
    # Check odd factors
    factor = 3
    while factor * factor <= n:
        while n % factor == 0:
            yield factor
            n //= factor
        factor += 2
    
    # If n > 1, it's a prime
    if n > 1:
        yield n

def largest_prime_factor_generator(n):
    """Find largest prime factor using generator."""
    return max(prime_factors_generator(n))

Performance Analysis

Let’s test with our target number 600,851,475,143:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import time

def benchmark_solution(func, n):
    start = time.time()
    result = func(n)
    end = time.time()
    return result, end - start

# Test all solutions
n = 600_851_475_143

# Using primePy (if available)
# result1, time1 = benchmark_solution(lambda x: max(primes.factorise(x)), n)

# Pure Python solutions
result2, time2 = benchmark_solution(largest_prime_factor_basic, n)
result3, time3 = benchmark_solution(largest_prime_factor_optimized, n)
result4, time4 = benchmark_solution(largest_prime_factor_efficient, n)

Results:

Why External Libraries Can Be Great

Your solution showcases an important programming principle: leverage existing, well-tested code!

Advantages of using primePy:

  1. Highly optimized - written by experts in number theory
  2. Well-tested - handles edge cases you might miss
  3. Readable - intent is crystal clear
  4. Maintainable - updates come automatically

When to use libraries vs. custom code:

Mathematical Insights

Why We Only Check Up to $\sqrt{n}$

If $n$ has a factor greater than $\sqrt{n}$, it must be paired with a factor less than $\sqrt{n}$:

The Special Case: Large Prime Remainders

After removing all small prime factors, if $n > 1$ remains, then $n$ itself is prime:

1
2
3
4
5

# Example: 77 = 7 × 11
n = 77
# Remove factor 7: n becomes 11
# 11 > 1 and no factors found up to √11 ≈ 3.3
# Therefore 11 is prime and our largest factor!

Complete Working Solutions

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# Solution 1: Using primePy (your approach)
from primePy import primes

def solve_euler_3_library():
    return max(primes.factorise(600_851_475_143))

# Solution 2: Pure Python (most efficient)
def solve_euler_3_pure():
    def largest_prime_factor(n):
        largest = 1
        
        # Handle factor 2
        if n % 2 == 0:
            largest = 2
            while n % 2 == 0:
                n //= 2
        
        # Check odd factors
        i = 3
        while i * i <= n:
            if n % i == 0:
                largest = i
                while n % i == 0:
                    n //= i
            i += 2
        
        if n > 1:
            largest = n
            
        return largest
    
    return largest_prime_factor(600_851_475_143)

if __name__ == "__main__":
    # Test both approaches
    print(f"Using primePy: {solve_euler_3_library()}")
    print(f"Pure Python: {solve_euler_3_pure()}")
    
    # Verify with smaller example
    test_n = 13195
    print(f"Test with 13195: {largest_prime_factor(13195)}")  # Should be 29

Key Takeaways

  1. Libraries can dramatically simplify solutions - your one-liner is elegant!
  2. Understanding the underlying algorithm is still valuable for learning
  3. Trial division works by testing potential factors systematically
  4. Mathematical optimizations (like √n limit) can provide huge speedups
  5. Different approaches suit different contexts (library vs. custom code)

Test Your Understanding

  1. Find the largest prime factor of 1,000,000
  2. What’s the sum of all prime factors of 600,851,475,143?
  3. Can you modify the generator solution to return factors in descending order?

This is part of my Python Problem Solving series. Check out more solutions on my GitHub!