#Skip to menu

Summation of primes

First read the problem description.

We’ll use the dual algorithm explained in Linear prime-number sieves: a family tree to generate the primes. The primes themselves will be stored inside a bit array.

import array

def primes_upto(N):
    S = array.array('B')
    S.extend(0 for x in range((N >> 3) + 1))
    def set_bit(i):
        S[i>>3] |= 1<<(i&7)
    def is_bit_set(i):
        return S[i>>3]&(1<<(i&7)) 
    
    f = 2
    while f*2 <= N:
        p = 2
        pOK = True
        while pOK:
            set_bit(f*p)
            t = p
            p += 1
            while is_bit_set(p):
                p += 1
            pOK = f*p <= N and (f % t != 0)
        f += 1
        
    for i in range(2, N+1):
        if not is_bit_set(i):
            yield i

sum(primes_upto(2_000_000))
142913828922

See what people say about this article.


Source code of the solution(s):