Project Euler Problems 1-5: Solutions With Math & Python

TL;DR

Project Euler problems 1-5 teach fundamental algorithmic and mathematical concepts: divisibility rules, sequence generation, prime factorization, and number theory. We'll solve each with brute-force approaches first, then optimize using mathematical insights like arithmetic series formulas and the Sieve of Eratosthenes.

Project Euler is a legendary collection of computational math problems that bridge pure mathematics and practical programming. The early problems (1-5) are deceptively simple: they look like homework exercises but hide deep algorithmic lessons. Solving them efficiently teaches you optimization techniques—memoization, mathematical shortcuts, and algorithmic thinking—that scale to harder problems.

In this guide, we'll work through problems 1 through 5, showing both the naive brute-force solution and the mathematically optimized version for each. You'll see how understanding the math behind a problem can reduce runtime from O(n) to O(1), and why Project Euler matters in 2026 as a training ground for interview preparation and algorithmic problem-solving.

Problem 1: Sum of Multiples

The Problem: Find the sum of all multiples of 3 or 5 below 1000.

This is pure divisibility: iterate through 1-999, check if each number divides evenly by 3 or 5, and sum the matches.

Brute Force Solution:

def sum_multiples_bruteforce(limit: int) -> int:
    """O(n) solution: iterate and check divisibility."""
    total = 0
    for i in range(limit):
        if i % 3 == 0 or i % 5 == 0:
            total += i
    return total

result = sum_multiples_bruteforce(1000)
print(result)  # 233168

Time: O(n), Space: O(1). Simple, correct, but slow for large limits.

Optimized Solution (Arithmetic Series):

The key insight: multiples of 3 below 1000 form an arithmetic sequence (3, 6, 9, ..., 999). The sum of an arithmetic sequence is n * (first + last) / 2, where n is the count.

• Multiples of 3: count = ⌊999/3⌋ = 333, sum = 333 * (3 + 999) / 2 = 166833
• Multiples of 5: count = ⌊999/5⌋ = 199, sum = 199 * (5 + 995) / 2 = 99500
• Multiples of 15 (overlap): count = ⌊999/15⌋ = 66, sum = 66 * (15 + 990) / 2 = 33165

def sum_multiples_optimized(limit: int) -> int:
    """O(1) solution using arithmetic series."""
    def arithmetic_sum(divisor: int, ceiling: int) -> int:
        """Sum of multiples of divisor below ceiling."""
        n = (ceiling - 1) // divisor
        first = divisor
        last = n * divisor
        return n * (first + last) // 2

    sum_3 = arithmetic_sum(3, limit)
    sum_5 = arithmetic_sum(5, limit)
    sum_15 = arithmetic_sum(15, limit)

    return sum_3 + sum_5 - sum_15

result = sum_multiples_optimized(1000)
print(result)  # 233168

Complexity: O(1) vs O(n). For limit=1,000,000, brute force does 1M iterations; optimized does 6 arithmetic operations.

---

Problem 2: Sum of Even Fibonacci Numbers

The Problem: Find the sum of all even Fibonacci numbers below 4 million.

The Fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21, ...) generates every third number that's even (2, 8, 34, ...). We need their sum.

Brute Force Solution:

def even_fibonacci_sum_bruteforce(limit: int) -> int:
    """O(n) solution: generate all Fibs, filter evens, sum."""
    a, b = 1, 1
    total = 0

    while b < limit:
        if b % 2 == 0:
            total += b
        a, b = b, a + b

    return total

result = even_fibonacci_sum_bruteforce(4_000_000)
print(result)  # 4613732

Time: O(log n) for generating Fibs (exponential growth), Space: O(1).

Optimized Solution (Every Third Fibonacci):

A mathematical property: every third Fibonacci number is even. If F(n) denotes the nth Fibonacci number, then F(3k) is always even.

So instead of generating all Fibs and filtering, generate every third directly:

• E(n) = nth even Fibonacci
• E(1) = 2, E(2) = 8, E(3) = 34
• Recurrence: E(n) = 4 * E(n-1) + E(n-2)

def even_fibonacci_sum_optimized(limit: int) -> int:
    """Skip to every third Fibonacci directly."""
    a, b = 2, 8  # First two even Fibs
    total = a

    while b < limit:
        total += b
        a, b = b, 4 * b + a  # Recurrence for even Fibs

    return total

result = even_fibonacci_sum_optimized(4_000_000)
print(result)  # 4613732

Complexity: Same O(log n) for iteration, but ~3x fewer iterations (every third instead of every Fibonacci). The optimization is constant-factor, not asymptotic, but practical for limit=4M.

---

Problem 3: Largest Prime Factor

The Problem: What is the largest prime factor of 600851475143?

Prime factorization: decompose a number into its prime divisors. The brute-force approach divides by candidate factors; the optimized approach only checks up to √n and uses trial division efficiently.

Brute Force Solution:

def largest_prime_factor_bruteforce(n: int) -> int:
    """O(n) worst case: trial division by all candidates."""
    factor = n

    # Remove factor 2
    while n % 2 == 0:
        factor = 2
        n //= 2

    # Try odd candidates up to n
    i = 3
    while i * i <= n:
        while n % i == 0:
            factor = i
            n //= i
        i += 2

    # If n > 1, then n itself is prime
    if n > 1:
        factor = n

    return factor

result = largest_prime_factor_bruteforce(600851475143)
print(result)  # 6857

Time: O(√n), Space: O(1). We only iterate up to √n because if n has a factor > √n, it has exactly one (paired with a factor < √n).

Optimized Solution (Segmented Trial Division):

For most numbers, trial division up to √n is sufficient. The optimization here is constant-factor: we skip even numbers after 2, and use efficient modulo operations.

def largest_prime_factor_optimized(n: int) -> int:
    """Optimized trial division up to sqrt(n)."""
    largest = -1

    # Check factor 2
    while n % 2 == 0:
        largest = 2
        n //= 2

    # Check odd factors from 3 onwards
    i = 3
    while i * i <= n:
        while n % i == 0:
            largest = i
            n //= i
        i += 2

    # Remaining n (if > 1) is prime
    if n > 1:
        largest = n

    return largest

result = largest_prime_factor_optimized(600851475143)
print(result)  # 6857

Complexity: Both are O(√n). The difference is constant factors: the optimized version skips even numbers. For n=600851475143, √n ≈ 775,146, so we iterate ~390K times instead of 775K.

---

Problem 4: Largest Palindrome Product

The Problem: Find the largest palindromic number that is the product of two 3-digit numbers.

A palindrome reads the same forwards and backwards (121, 1331, 12321). We need the largest one formed by multiplying two numbers from 100-999.

Brute Force Solution:

def is_palindrome(n: int) -> bool:
    """Check if n reads the same forwards and backwards."""
    s = str(n)
    return s == s[::-1]

def largest_palindrome_bruteforce() -> int:
    """O(n²): try all pairs, check palindrome for each."""
    largest = 0

    for i in range(100, 1000):
        for j in range(i, 1000):  # j >= i to avoid duplicates
            product = i * j
            if is_palindrome(product) and product > largest:
                largest = product

    return largest

result = largest_palindrome_bruteforce()
print(result)  # 906609

Time: O(n²) where n=900 (range of 3-digit numbers), so ~810,000 iterations. Space: O(1).

Optimized Solution (Iterate One Factor Downward):

Key insight: instead of checking all products, iterate one factor downward from 999, computing products, and track the maximum palindrome found. This skips many pairs without checking them.

def largest_palindrome_optimized() -> int:
    """O(n²) but with early termination: iterate outer factor down."""

    def is_palindrome(n: int) -> bool:
        s = str(n)
        return s == s[::-1]

    max_palindrome = 0

    # Iterate i from 999 downward; once i*999 < max, stop
    for i in range(999, 99, -1):
        if i * 999 < max_palindrome:
            break
        for j in range(999, i - 1, -1):
            product = i * j
            if product < max_palindrome:
                break
            if is_palindrome(product):
                max_palindrome = product

    return max_palindrome

result = largest_palindrome_optimized()
print(result)  # 906609

Complexity: Still O(n²) in worst case, but with early termination when products drop below the known max palindrome. For this problem, the speedup is ~2-3x due to pruning."""

---

Problem 5: Smallest Number Divisible by 1-20

The Problem: What is the smallest positive number divisible by all integers from 1 to 20?

This is the least common multiple (LCM). Brute force increments until finding a number divisible by all; optimized uses prime factorization and the LCM formula.

Brute Force Solution:

def smallest_divisible_bruteforce() -> int:
    """O(n * m): iterate n, check divisibility by 1-20."""
    n = 1

    while True:
        if all(n % i == 0 for i in range(1, 21)):
            return n
        n += 1

result = smallest_divisible_bruteforce()
print(result)  # 232792560

Time: O(lcm(1..20)) = O(232,792,560), very slow. Space: O(1).

Optimized Solution (Prime Factorization + LCM):

The LCM is the product of the highest prime powers in the factorizations:

• LCM(1..20) = 2⁴ × 3² × 5 × 7 × 11 × 13 × 17 × 19
• = 16 × 9 × 5 × 7 × 11 × 13 × 17 × 19 = 232,792,560

from math import gcd

def lcm(a: int, b: int) -> int:
    """Least common multiple: lcm(a,b) = a*b / gcd(a,b)."""
    return (a * b) // gcd(a, b)

def smallest_divisible_optimized() -> int:
    """O(n log n): compute LCM of 1-20."""
    result = 1
    for i in range(1, 21):
        result = lcm(result, i)
    return result

result = smallest_divisible_optimized()
print(result)  # 232792560

Alternative (direct prime factorization):

def smallest_divisible_primes() -> int:
    """O(1): hardcode highest prime powers up to 20."""
    # Prime factorizations:
    # 2: 2^4 (from 16)
    # 3: 3^2 (from 9)
    # 5: 5^1
    # 7: 7^1
    # 11: 11^1
    # 13: 13^1
    # 17: 17^1
    # 19: 19^1
    return 2**4 * 3**2 * 5 * 7 * 11 * 13 * 17 * 19

result = smallest_divisible_primes()
print(result)  # 232792560

Complexity: Optimized is O(n log n) where n=20 (for GCD calculations), vastly faster than O(232M) brute force.

---

Key Takeaways

1. Arithmetic properties reduce complexity: Problem 1 drops from O(n) to O(1) using arithmetic series formulas.
2. Recognize patterns: Problem 2's "every third Fibonacci" pattern is a 3x speedup.
3. Square-root tricks: Problem 3 leverages √n factorization bounds.
4. Work backwards for optimization: Problem 4 descends from the max to find the answer faster.
5. Use number theory: Problem 5's LCM formula solves in microseconds instead of seconds.

These early problems establish the foundation for harder challenges. As you progress through Project Euler, these techniques—divisibility, factorization, sequences, and modular arithmetic—become standard tools.

Conclusion

Project Euler problems 1-5 are the gateway to computational thinking. They're straightforward enough to solve naively, but rich enough to teach lasting optimization principles. Whether you're training for interviews, reinforcing your math fundamentals, or simply enjoying algorithmic puzzles, these problems reward both brute-force persistence and mathematical insight.

The transition from brute force to optimized solutions mirrors the journey of becoming a better programmer: recognize structure, apply theory, and express elegance in code. Start with problems 1-5, then move forward with confidence.