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):
= array.array('B')
S 0 for x in range((N >> 3) + 1))
S.extend(def set_bit(i):
>>3] |= 1<<(i&7)
S[idef is_bit_set(i):
return S[i>>3]&(1<<(i&7))
= 2
f while f*2 <= N:
= 2
p = True
pOK while pOK:
*p)
set_bit(f= p
t += 1
p while is_bit_set(p):
+= 1
p = f*p <= N and (f % t != 0)
pOK += 1
f
for i in range(2, N+1):
if not is_bit_set(i):
yield i
sum(primes_upto(2_000_000))
142913828922
Source code of the solution(s):