## Question

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

Find the sum of all the primes below two million.

## Clojure

#!/usr/bin/env clojure
(defn primes [n]
(defn improve [p nums]
(filter #(or
(not (= (rem % p) 0))
(= % p))
nums))
(defn prime-iter [p nums i]
(if (> (* p p) n)
nums
(prime-iter (nth nums (+ i 1)) (improve (nth nums (+ i 1)) nums) (+ i 1))))
(prime-iter 2 (range 2 (+ n 1)) -1))

(println (reduce + (primes 2000000)))
$time ./sum-primes real 0m1.088s user 0m1.072s sys 0m0.000s ## JavaScript const sieve = {} let s = 0 for (let q = 2; q < 2000000; q++) { if (sieve[q]) { sieve[q].forEach((p) => { const list = sieve[p + q] || [] list.push(p) sieve[p + q] = list }) delete sieve[q] } else { s += q sieve[q * q] = [q] } } console.log(s) $ time node --use-strict --harmony-destructuring sum-primes.js
real   0m3.678s
user   0m3.576s
sys    0m0.036s

## Python

#!/usr/bin/env python
from itertools import takewhile

def eratosthenes():
'''Yields the sequence of prime numbers via the Sieve of Eratosthenes.'''
D = {}  # map composite integers to primes witnessing their compositeness
q = 2   # first integer to test for primality
while 1:
if q not in D:
yield q        # not marked composite, must be prime
D[q*q] = [q]   # first multiple of q not already marked
else:
for p in D[q]: # move each witness to its next multiple
D.setdefault(p+q,[]).append(p)
del D[q]       # no longer need D[q], free memory
q += 1

print(sum(takewhile(lambda x: x < 2000000, eratosthenes())))
$time python3 sum-primes.py real 0m2.096s user 0m2.024s sys 0m0.036s ## Ruby #!/usr/bin/env ruby require 'mathn' puts Prime.take_while{ |n| n < 2000000 }.reduce(:+) $ time ruby sum-primes.rb
real   0m0.326s
user   0m0.320s
sys    0m0.004s