Problem 10: Summation of Primes

At first glance, you may think of checking each number below two million individually for primality, but that would be painfully inefficient. However, we can, in fact, borrow a technique from earlier, the Sieve of Eratosthenes.

In terms of python:

limit = 2000000
sieve = [True] * limit
sieve[0:2] = [False, False]
for i in range(2, int(limit ** 0.5) + 1):
    if sieve[i]:
        sieve[i*i : limit : i] = [False] * len(range(i*i, limit, i))
    
primes = [i for i, is_prime in enumerate(sieve) if is_prime]
print(sum(primes))

Explained line by line:

• We set a variable limit to two million, which is the upper bound for our search for prime numbers.
• We create a list called sieve initialized to True, indicating that all numbers are initially assumed to be prime. We set the first two entries (0 and 1) to False since they are not prime.
• We then iterate through each number starting from 2 up to the square root of the limit. For each prime number found, we mark all its multiples as False (not prime).
• After constructing the sieve, we create a list of all indices that are still marked as True, which correspond to prime numbers.
• Finally, we calculate the sum of all the prime numbers in the list and print the result.

Running the above code leads to an answer of $142913828922$