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 clojuredefn primes [n]
(defn improve [p nums]
(filter #(or
(not (= (rem % p) 0))
(= % p))
(
nums))defn prime-iter [p nums i]
(if (> (* p p) n)
(
numsnth nums (+ i 1)) (improve (nth nums (+ i 1)) nums) (+ i 1))))
(prime-iter (2 (range 2 (+ n 1)) -1))
(prime-iter
println (reduce + (primes 2000000))) (
$ time clojure sum-primes.clj
real 0m4.080s
user 0m5.068s
sys 0m0.254s
Go
package main
import "fmt"
import "math"
func PrimeSieve(n int64) []int64 {
:= make([]int64, 0, n/int64(math.Log(float64(n))))
result := make([]bool, n+1)
sieve := int64(math.Sqrt(float64(n)))
sn var i, j int64
for i = 2; i <= sn; i++ {
if !sieve[i] {
for j = i * i; j <= n; j += i {
[j] = true
sieve}
}
}
for i = 2; i <= n; i++ {
if !sieve[i] {
= append(result, i)
result }
}
return result
}
func main() {
:= PrimeSieve(2000000)
primes var sum int64 = 0
for _, p := range primes {
+= p
sum }
.Println(sum)
fmt}
$ go build -o sum-primes sum-primes.go
$ time ./sum-primes
real 0m0.009s
user 0m0.011s
sys 0m0.000s
Haskell
primes :: [Integer]
= 2 : sieve primes [3,5..] where
primes :ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
sieve (pwhere (h, t) = span (< p*p) xs
main :: IO ()
= print $ sum $ takeWhile (< 2000000) primes main
$ ghc -O2 -o sum-primes sum-primes.hs
$ 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]) {
.forEach((p) => {
sieve[q]const list = sieve[p + q] || []
.push(p)
list+ q] = list
sieve[p
})delete sieve[q]
else {
} += q
s * q] = [q]
sieve[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.'''
= {} # map composite integers to primes witnessing their compositeness
D = 2 # first integer to test for primality
q while 1:
if q not in D:
yield q # not marked composite, must be prime
*q] = [q] # first multiple of q not already marked
D[qelse:
for p in D[q]: # move each witness to its next multiple
+q,[]).append(p)
D.setdefault(pdel D[q] # no longer need D[q], free memory
+= 1
q
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 {
= false;
sieve[i] += p;
i }
// Find the next prime.
if let Some(n) = (p..limit).find(|&n| sieve[n]) {
= n + 1;
p } 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