Project Euler Problem 10 Solution

Question

The sum of the primes below 10 is 2+3+5+7=172 + 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 clojure sum-primes.clj
real   0m4.286s
user   0m4.860s
sys    0m0.204s

Go

package main

import "fmt"
import "math"

func PrimeSieve(n int64) []int64 {
    result := make([]int64, 0, n/int64(math.Log(float64(n))))
    sieve := make([]bool, n+1)
    sn := int64(math.Sqrt(float64(n)))
    var i, j int64
    for i = 2; i <= sn; i++ {
        if !sieve[i] {
            for j = i * i; j <= n; j += i {
                sieve[j] = true
            }
        }
    }
    for i = 2; i <= n; i++ {
        if !sieve[i] {
            result = append(result, i)
        }
    }
    return result
}

func main() {
    primes := PrimeSieve(2000000)
    var sum int64 = 0
    for _, p := range primes {
        sum += p
    }
    fmt.Println(sum)
}
$ go build -o sum-primes sum-primes.go
$ time ./sum-primes
real   0m0.012s
user   0m0.008s
sys    0m0.000s

Haskell

primes :: [Integer]
primes = 2 : sieve primes [3,5..] where
    sieve (p:ps) xs = h ++ sieve ps [x | x <- t, rem x p /= 0]
                      where (h, t) = span (< p*p) xs

main :: IO ()
main = print $ sum $ takeWhile (< 2000000) primes
$ ghc -O2 -o sum-primes sum-primes.hs
$ 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