Problem Analysis
The task is to add up every prime below two million. The arithmetic is trivial — a single
running sum — so the entire difficulty lies in enumerating the primes quickly. By the
prime number theorem
there are about n / ln n primes below n, so for n = 2,000,000
we are summing roughly 148,933 numbers; the answer, 142,913,828,922, overflows 32 bits and must
be accumulated in a 64-bit integer (Python integers are unbounded, so this only bites the C side).
The decisive question is how cheaply each prime can be found. Testing each candidate independently
by
trial division
costs O(√n) per number and O(n√n / ln n) overall — correct
but slow. A sieve flips the economics: instead of interrogating each number, it crosses off the
multiples of primes it has already found, sharing work across the whole range. The classical
Sieve of Eratosthenes
runs in O(n log log n) time — effectively linear — which is the complexity class
that makes this problem easy at two million and still comfortable at ten million. I implemented
five solutions to contrast the approaches: a
Sieve of Eratosthenes,
a
Sieve of Sundaram,
an unbounded incremental sieve, plain
trial division,
and a call into a specialised C library.
Solution Approach
Solution 0 — Sieve of Eratosthenes
My baseline is the
Sieve of Eratosthenes.
I allocate a bytearray of max_num + 1 flags initialised to 1, clear
indices 0 and 1, then for each i up to √max_num that is still
marked prime I clear every multiple starting at i*i (smaller multiples were already
cleared by smaller primes). The remaining set indices are the primes, and I sum them. The Python
version leans on a key trick: the inner loop is replaced by the slice assignment
sieve[i*i::i] = bytearray(len(...)), which clears a whole arithmetic progression in
one C-level operation. The C sibling writes the inner loop explicitly over an
unsigned char array. Time is O(n log log n), space O(n).
Solution 1 — Sieve of Sundaram
The
Sieve of Sundaram
sieves only the odd numbers. It works on indices i ≤ n = (max_num - 1) / 2, where
index k represents the odd number 2k + 1. The insight is that an odd
number 2k + 1 is composite exactly when k can be written as
i + j + 2ij for some 1 ≤ i ≤ j, because
2(i + j + 2ij) + 1 = (2i + 1)(2j + 1). So I mark every i + j + 2ij, then
every unmarked index i yields the prime 2i + 1 (with 2 prepended). It is
a tidy reformulation of the same sieving idea on a half-sized array; in practice its bound is a
touch looser than Eratosthenes, around O(n log n). Python and C implement the marking
loop identically.
Solution 2 — Unbounded incremental sieve
Solution 2 is an unbounded
Sieve of Eratosthenes
expressed as a
generator function.
Rather than allocating the full table up front, it keeps a dictionary mapping the next composite
each known prime will strike to that prime's step. When the running counter n is
absent from the map it is prime, and I schedule its first multiple n*n; when it is
present I advance that prime's entry to its next free odd multiple. This yields primes lazily in
order, so solve() can stop the instant a prime reaches max_num without
knowing the bound in advance. The C translation reproduces the dictionary with a hand-written
hash table using
open addressing,
including the cluster-rehash needed after a deletion. The time complexity matches the array sieve,
O(n log log n), but the constant factor is far worse because of per-number map churn.
Solution 3 — Trial division
Solution 3 is the deliberately naive baseline:
trial division.
For each candidate below max_num I test divisibility by 2 and then by odd numbers up
to √num; the first divisor found proves compositeness. It needs no extra memory
beyond the loop variables, which is its only virtue here. The cost is O(n√n / ln n),
and the timings below show exactly how badly that scales against the sieves. Python and C share
the same is_prime structure.
Solution 4 — primesieve library
Solution 4 delegates to
primesieve,
a highly optimised segmented sieve that uses
wheel factorization
and cache-friendly segmentation to enumerate primes at close to memory bandwidth. The Python code
is a one-liner over primesieve.primes(max_num - 1); the C code calls
primesieve_generate_primes over [2, max_num - 1] and sums the array. Both
pass max_num - 1 so the upper endpoint stays strictly below max_num, as
the problem demands. This is the fastest of the five and shows what a purpose-built library buys
over a hand-rolled
Sieve of Eratosthenes.