# Project Euler Problem 10 Solution

## 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.046s user 0m1.038s sys 0m0.008s ## 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 sum-primes.js
real   0m1.446s
user   0m1.977s
sys    0m0.054s

## 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.099s user 0m2.060s sys 0m0.039s ## Ruby #!/usr/bin/env ruby require 'mathn' puts Prime.take_while{ |n| n < 2000000 }.reduce(:+) $ time ruby sum-primes.rb
real   0m0.223s
user   0m0.191s
sys    0m0.032s

## Rust

fn eratosthenes(limit: usize) -> Vec<usize> {
let mut sieve = vec![true; limit];
let mut p = 2;
loop {
// Eliminate multiples of p.
let mut i = 2 * p - 1;
while i < limit {
sieve[i] = false;
i += p;
}
// Find the next prime.
if let Some(n) = (p..limit).find(|&n| sieve[n]) {
p = n + 1;
} else {
break;
}
}
sieve
.iter()
.enumerate()
.filter(|&(_, &is_prime)| is_prime)
.skip(1)
.map(|(i, _)| i + 1)
.collect()
}

fn main() {
let sum: usize = eratosthenes(2000000).iter().sum();
println!("{}", sum);
}
$rustc -C target-cpu=native -C opt-level=3 -o primes primes.rs$ time ./primes
real   0m0.014s
user   0m0.014s
sys    0m0.000s