Project Euler Problem 10

Solution

To solve this efficiently, we need the sum of all primes less than $2{,}000{,}000$.

A direct primality test on every number would be too slow. The standard approach is the Sieve of Eratosthenes, which marks multiples of each prime as composite.

The idea:

Create a boolean array is_prime from 0 to 1,999,999.
Initially assume all numbers $\ge 2$ are prime.
For each prime $p$, mark all multiples of $p$ starting at $p^2$ as non-prime.
Sum all remaining prime indices.

The complexity is approximately $O(n \log \log n)$, which is fast enough for two million.

Python code:

limit = 2_000_000

is_prime = [True] * limit
is_prime[0] = is_prime[1] = False

p = 2
while p * p < limit:
    if is_prime[p]:
        for multiple in range(p * p, limit, p):
            is_prime[multiple] = False
    p += 1

total = sum(i for i, prime in enumerate(is_prime) if prime)

print(total)

Tracing correctness on the small example:

Primes below $10$ are:

$$2,3,5,7$$

Their sum is:

$$2+3+5+7=17$$

which matches the statement.

Running the sieve up to two million produces:

Answer: 142913828922