Summation of primes

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Idea

A problem of 'big number primality check'.

Refer to a method called Miller–Rabin_primality_test

Simple primality check will run timeout... :<

In [1]:
from math import sqrt
In [2]:
def _try_composite(a, d, n, s):
    if pow(a, d, n) == 1:
        return False
    for i in range(s):
        if pow(a, 2**i * d, n) == n-1:
            return False
    return True
In [3]:
def is_prime(n):
    if n in _known_primes:
        return True
    if any((n % p) == 0 for p in _known_primes):
        return False
    d, s = n - 1, 0
    while not d % 2:
        d, s = d >> 1, s + 1
    # Returns exact according to http://primes.utm.edu/prove/prove2_3.html
    if n < 1373653: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3))
    if n < 25326001: 
        return not any(_try_composite(a, d, n, s) for a in (2, 3, 5))
In [4]:
_known_primes = [2, 3]
_known_primes += [x for x in range(5, 1000, 2) if is_prime(x)]
In [5]:
is_prime(4)
Out[5]:
False
In [6]:
is_prime(11)
Out[6]:
True
In [7]:
def generate_prime():
    primes = [2, 3, 5, 7]
    for p in primes:
        yield p
    higher_digit = 1
    while True:
        for i in [1, 3, 7, 9]:
            candidate = higher_digit * 10 + i
            if is_prime(candidate):
                yield candidate
        higher_digit += 1
In [8]:
def solve(bound):
    result = 0
    for p in generate_prime():
        if p > bound:
            break
        result += p
    return result
In [9]:
solve(10)
Out[9]:
17
In [10]:
solve(2e6)
Out[10]:
142913828922