---
title: 'Project Euler Problems 1-5: Solutions With Math & Python'
description: 'Project Euler problems 1-5: divisibility, Fibonacci, primes, palindromes, LCM. See brute-force vs optimized Python solutions with complexity analysis.'
url: https://nerdleveltech.com/how-to-solve-project-euler-problems-1-5
language: en
date: '2023-01-15'
updated: '2026-03-27'
category: backend
tags:
  - project-euler
  - algorithms
  - python
  - mathematics
markdown_url: https://nerdleveltech.com/how-to-solve-project-euler-problems-1-5.md
attribution: 'Source: NerdLevelTech — https://nerdleveltech.com/how-to-solve-project-euler-problems-1-5'
terms: https://nerdleveltech.com/llms.txt
---

# 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.

## Introduction

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:**

```python
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

By inclusion-exclusion: sum(3 or 5) = sum(3) + sum(5) - sum(15) = 166833 + 99500 - 33165 = 233168

```python
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:**

```python
def even_fibonacci_sum_bruteforce(limit: int) -> int:
    """O(log limit) solution: generate Fibs (which grow exponentially), 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 limit) — Fibonacci numbers grow exponentially, so the count of Fibs below `limit` is logarithmic. 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)`

```python
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 limit) 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:**

```python
def largest_prime_factor_bruteforce(n: int) -> int:
    """O(n) worst case: trial division by every integer up to n."""
    largest = 1
    for i in range(2, n + 1):
        while n % i == 0:
            largest = i
            n //= i
        if n == 1:
            break
    return largest

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

Time: O(n) in the worst case (when `n` is prime), Space: O(1). This works but is too slow for large inputs — for n ≈ 6×10^11 it would do hundreds of billions of iterations before finishing.

**Optimized Solution (Trial Division up to √n):**

The key insight: if `n` has a factor greater than √n, it has at most one such factor (paired with a factor below √n). So we only need to trial-divide up to √n. We also skip even numbers after handling 2 explicitly.

```python
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:** O(√n) vs O(n) for brute force. For n=600851475143, √n ≈ 775,146, so the optimized version iterates roughly 390K times (skipping evens) instead of trial-dividing through ~6×10^11 candidates.

---

## 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:**

```python
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.

```python
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:**

```python
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(k * lcm(1..20)) where k=20 (divisors checked per candidate) — roughly 4.6 billion operations on this input. 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

```python
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):

```python
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 (each `gcd` is O(log result) and result grows to ~232M), vastly faster than the brute-force O(k · lcm) ≈ 4.6 billion operations.

---

## 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.

[^project-euler]: Project Euler. https://projecteuler.net/