Project Euler Problem 10

Problem 10

08 February 2002

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

Find the sum of all the primes below two million.

Answer: 142913828922

 

 

C#

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Euler {
    class Program {
        static void Main(string[] args) {
            const long pmax = 2000000;

            bool[] isPrime = new bool[pmax];
            for (long i = 2; i < pmax; i++) {
                isPrime[i] = true;
            }

            {
                const long i = 2;
                for (long j = 2 * i; j < pmax; j += i) {
                    isPrime[j] = false;
                }
            }

            for (int i = 3; i * i<= pmax; i += 2) {
                if (!isPrime[i]) continue;
                for (long j = 2 * i; j < pmax; j += i) {
                    isPrime[j] = false;
                }                
            }

            long sum = 0;
            for (int i = 2; i < pmax; i++) {
                if (isPrime[i]) sum += i;
            }
            Console.WriteLine(sum);
        }
    }
}

Perl

sub primesUnder {
 my ($limit) = @_;
 my @p = 0 x $limit;
 if ( $limit >= 3 ) { $p[2] = 1; }
 for ( my $i = 3 ; $i < $limit ; $i += 2 ) { $p[$i] = 1; }
 for ( my $i = 3 ; $i * $i < $limit ; $i += 2 ) {
  if ( !$p[$i] ) { next; }
  for ( my $j = $i * 2 ; $j < $limit ; $j += $i ) {
   $p[$j] = 0;
  }
 }

 my @r = ();
 for my $i ( 2 .. $limit - 1 ) {
  if ( $p[$i] ) { push( @r, $i ); }
 }
 return @r;
}

sub problem10 {
 print sum( primesUnder(2000000) );
}

problem10();

Python

import math

def primesUnder(limit):
    p = [0] * limit
    if limit >= 3: p[2] = True      
    for i in range(3, limit, 2): p[i] = True
    for i in range(3, int(math.sqrt(limit)), 2):
        if not p[i]: continue
        for j in range(i * 2, limit, i):
            p[j] = False
   
    r = []
    for i in range(2, limit, 1):
        if p[i]: r.append(i)
    return r

def problem10():
    print(sum(primesUnder(2000000)))

problem10()

Go

func primesUnder(limit int) []int {

    p := make([]bool, limit)

    if limit >= 3 {

        p[2] = true

    }

    for i := 3; i < limit; i += 2 {

        p[i] = true

    }

    for i := 3; i*i < limit; i += 2 {

        if !p[i] {

            continue

        }

        for j := i * 2; j < limit; j += i {

            p[j] = false

        }

    }

    r := []int{}

    for i := 2; i < limit; i++ {

        if p[i] {

            r = append(r, i)

        }

    }

    return r

}

func problem10() {

    var sum int64 = 0

    for _, i := range primesUnder(2000000) {

        sum += int64(i)

    }

    fmt.Println(sum)

}

func main() {

    problem10()    

} 

C++

vector<int> primesUnder(int limit) {

    vector<bool> p(limit);

    if (limit >= 3) {

        p[2] = true;

    }

    for (auto i = 3; i < limit; i += 2) {

        p[i] = true;

    }

    for (auto i = 3; i*i < limit; i += 2) {

        if (!p[i]) {

            continue;

        }

        for (auto j = i * 2; j < limit; j += i) {

            p[j] = false;

        }

    }

    vector<int> r;

    for (auto i = 2; i < limit; i++) {

        if (p[i]) {

            r.push_back(i);            

        }

    }

    return r;

}

void problem10() {

    long long sum = 0;

    auto primes = primesUnder(2000000);

    for (auto itr = primes.begin(); itr != primes.end(); itr++) {    

        sum += *itr;

    }

    cout << sum;    

}

 

Bash (really slow)

 

function primesUnder {
    local limit=$1
    if ((limit >= 3)); then
        p[2]=1
    fi
    local i
    local j
    for ((i=3; i < limit; i += 2)); do
        p[i]=1
    done
    for ((i=3; i*i < limit; i+= 2)); do
        if ((!p[i])); then
            continue
        fi
        for ((j=i*2; j<limit; j+=i)); do
            p[j]=0
        done
    done

    for ((i=2; i<limit; i++)); do
        if ((p[i])); then
            echo -n " $i"
        fi
    done
    echo
}

function problem10 {
    local sum=0
    local primes=$(primesUnder 2000000)
    echo $primes
    for x in $primes; do
        ((sum += x))
    done
    echo $sum
}

function problem10b {
    local sum=0
    local x
    for x in {2..2000000}; do
        if isPrime $x; then ((sum+=x)); fi
    done
    echo $sum
}

problem10b

 

Javascript

function primesUnder(limit) {
    var p = new Array(limit);
    if (limit >= 3) p[2] = true;
    for (var i = 3; i < limit; i += 2)
        p[i] = true;
    for (var i = 3; i*i < limit; i += 2) {
        if (!p[i]) continue;
        for (var j = i * 2; j < limit; j += i)
            p[j] = false;
    }

    var r = [];
    for (var i = 2; i < limit; i++)
        if (p[i]) r.push(i);         
    return r;
}

function problem10() {
    var sum = 0;
    var primes = primesUnder(2000000);
    for (var i=0; i<primes.length; i++) sum += primes[i];
    return sum;   
}

problem10()

 

Racket

#lang racket

(define (prime? n)

  (let loop ([i 2])

    (if (<= (* i i) n)      

        (if (= 0 (modulo n i)) #f

            (loop (add1 i)))

        #t)))

(define (problem10)

  (define sum 0)

  (for ([i (in-range 2 2000000)])

    (when (prime? i) (set! sum (+ sum i))))

  (displayln sum))

(define (primesUnder limit)

  (define p (make-vector limit #t))

  (let loop ([i 2])

    (when (< (* i i) limit)

      (when (vector-ref p i) 

        (for ([j (in-range (* i i) limit i)]) (vector-set! p j #f)))

      (loop (+ 1 i))))  

  (define r (list))

  (for ([i (in-range 2 limit)])

    (when (vector-ref p i) (set! r (cons i r))))

  r)

(define (sumPrimesUnder limit)

  (define p (make-vector limit #t))

  (for ([i (in-range 2 (sqrt limit))])

    (when (vector-ref p i) 

      (for ([j (in-range (* i i) limit i)]) (vector-set! p j #f))))

  (for/sum ([i (in-range 2 limit)]

            #:when (vector-ref p i))

    i))

(define (problem10a)

  (displayln (foldl + 0 (primesUnder 2000000))))

(define (problem10b)

  (displayln (sumPrimesUnder 2000000)))

(time (problem10))

(time (problem10a))

(time (problem10b))

* Clojure

(ns Euler.core (:gen-class))
(set! *warn-on-reflection* true)
(defn prime? [n]
  (loop [i 2]
    (if (<= (* i i) n)     
      (if (zero? (mod n i))
        false
        (recur (inc i)))
      true)))

(defn problem10 []
  (println (apply + (filter prime? (range 2 2000000)))))  

(defn primesUnder [limit]
  (let [p (transient (apply vector (repeat limit true)))]
    (doseq [i (range 2 (Math/sqrt limit))]
      (when (p i)
        (doseq [j (range (* 2 i) limit i)] (assoc! p j false))))
    (filter #(p %) (range 2 limit))))

(defmacro loopwhile [init-symbol init whilep step & body]
  `(loop [~init-symbol ~init]
     (when ~whilep ~@body (recur (+ ~init-symbol ~step)))))

(defn primesUnderb [limit]
  (let [p (boolean-array limit true)]
    (loopwhile i 2 (< i (Math/sqrt limit)) 1
               (when (aget p i)
                 (loopwhile j (* i 2) (< j limit) i (aset p j false))))
    (filter #(aget p %) (range 2 limit))))

(defn sum-primes-under [limit]
  (let [p (boolean-array limit true)]
    (loopwhile i 2 (< i (Math/sqrt limit)) 1
               (when (aget p i)
                 (loopwhile j (* i 2) (< j limit) i (aset p j false))))
    (loop [i 2, sum 0]
      (if (< i limit)
        (recur (inc i) (if (aget p i) (+ sum i) sum))
        sum))))

(defn problem10a []
  (println (apply + (primesUnder 2000000))))

(defn problem10b []
  (println (apply + (primesUnderb 2000000))))
(defn problem10c []
  (println (sum-primes-under 2000000)))

;(time (problem10))
;(time (problem10a))
;(time (problem10b))
(time (problem10c))

* newLISP

(define (sum-primes-under limit)
  (let (p (array limit '(true)))
    (for (i 2 (- (sqrt limit) 1))
      (when (p i)
        (for (j (* i 2) (- limit 1) i) (setf (p j) false))))
    (let (sum 0)
      (for (i 2 (- limit 1))
        (when (p i) (setq sum (+ sum i))))
      sum)))

(define (problem10c)
  (println (sum-primes-under 2000000)))

(time (problem10c))