Project Euler Solution 10: Summation of primes
This is part of the Project Euler series and about Problem 10: Summation of primes. We need to find the sum of all primes below two million.
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.
We can just use our prime generator from Solution 3: Largest prime factor
def _solution_generator() -> int: prime_sum = 0 for prime in prime_generator(): if prime < 2_000_000: prime_sum += prime return prime_sum
However, this doesn't converge fast enough. The problem is that the generating algorithm is O(N²) because it needs to check all the numbers for all the known prime factors. I do cache the generated primes, but that is not enough. We need something better.
Using the sieve from Solution 7: 10001st prime is a much better idea.
def solution_sieve() -> int: primes = prime_sieve(2_000_000) return sum(primes)
This produces 142,913,828,922 in 789 ms. That should be okay.