in Programming

Project Euler Problem 10 Solution: Clojure

Problem description, from Project Euler

Find the sum of all the primes below N.

Solution

Brute-forced it again, but it still runs in less than 30 seconds (at least on my MacBook Pro). This one was simple using the Sieve of Eratosthenes from problem 7.

The sieve, collapsed because it’s the same as from problem 7:

; a
; //en.wikipedia.org/wiki/Sieve_of_Eratosthenes
;1. Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),
;2. Initially, let p equal 2, the first prime number,
;3. While enumerating all multiples of p starting from p2, strike them off from the original list,
;4. Find the first number remaining on the list after p (it's the next prime); let p equal this number,
;5. Repeat steps 3 and 4 until p2 is greater than n.
;6. All the remaining numbers in the list are prime.
; returns a lazy-sequence of the multiples of n

(defn sieve-of-eratosthenes
    [n]
    ; step 1 Create a list of consecutive integers from two to n: (2, 3, 4, ..., n),

(defn sieve [rng p]
    ;(print "range: " rng "\n")
    (
        ; this lambda used to perform the actual recursion
        (fn [new-rng]
            ; step #5 Repeat steps 3 and 4 until p^2 is greater than n.
            (if (<= (* p p) n) 
                ; recurse
                (sieve new-rng 
                    ; step # 4 Find the first number remaining on the list after p 
                    ; (it's the next prime); let p equal this number,
                    (first (filter #(> % p) new-rng))
                    )
                ; end recursion otherwise
                new-rng
                )
            )
        ; this is an argument to the lambda above
        ; step #3 While enumerating all multiples of p starting from p2, 
        ; strike them off from the original list,
        (filter 
            #(or 
                (not= ; divisible by p
                    (rem % p) 
                    0
                    )
                ; greater than p^2
                (< % (* p p))
                )
                rng
            )
        )
    )

(sieve
    (range 2 n)
    2 ; step #2 Initially, let p equal 2, the first prime number
    )
)


The new code:
(defn problem10 [max-nbr]
    (reduce + (sieve-of-eratosthenes max-nbr)) ; brute!
    )

Comments are closed.