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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | ; 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 )) |
1 2 3 | (defn problem10 [max-nbr] (reduce + (sieve-of-eratosthenes max-nbr)) ; brute! ) |
Blog: Project Euler Problem… /programming/project-euler-problem-10-solution-clojure/ #clojure
This comment was originally posted on Twitter