Euler 10 in Python
I decided to take on Project Euler’s problem #10. Its statement goes like this:
The sum of the primes below 10 is .
Find the sum of all the primes below two million.
A Sieve of Eratosthenes finds every prime below the limit together instead of
running a separate divisibility test for every number. A bytearray stores one
byte per candidate and supports crossing out a whole arithmetic progression at
once.
from math import isqrt
limit = 2_000_000
sieve = bytearray(b"\x01") * limit
sieve[:2] = b"\x00\x00"
for prime in range(2, isqrt(limit - 1) + 1):
if not sieve[prime]:
continue
start = prime * prime
count = (limit - 1 - start) // prime + 1
sieve[start:limit:prime] = b"\x00" * count
print(sum(number for number, is_prime in enumerate(sieve) if is_prime))
Starting at prime * prime is sufficient because smaller multiples already
have a smaller prime factor. The sieve runs in time, uses
space, and prints 142913828922.