Problem Description, from Project Euler
What is the n-th prime number?
Problem Solution
This was simple to solve using the Sieve created for the solution to problem #3. To make the program variable, we start with finding all primes less than 1000. If that is not enough to solve the problem, we double this “maximum” value, and search for all primes less than 2000. Rinse, repeat.
The old stuff:
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 54 | ; //en.wikipedia.org/wiki/Sieve_of_Eratosthenes(defn multiples [n] (lazy-cat [1 n] (map (fn [a] (+ a n)) (rest (multiples 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 stuff:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | (defn problem07 [nth] (defn try-find-nth-prime [primes max-number] (if (< (count primes) nth) ; if the list of primes is not long enough, ; double the maximum search number (try-find-nth-prime (sieve-of-eratosthenes (* max-number 2)) (* max-number 2) ) ; otherwise, take the nth member of the list (last (take nth primes)) ) )(try-find-nth-prime (sieve-of-eratosthenes 1000) 1000)) |
Blog: Project Euler Prob… //bit.ly/baij5T #clojure #projecteuler
This comment was originally posted on Twitter
Hi Jamie,
I’m enjoying your euler series so far. Concerning you way of putting parentheses consider reading //stackoverflow.com/questions/1894209/how-to-read-mentally-lisp-clojure-code. It can be tempting to think that it is easier to understand the code if you’re coming from a Java/C# background, but in fact it’s a little irritating
Otherwise, keep up the good work!
Matt
Hi Matt, I definitely see what you mean. Thanks for linking to an awesome post. I will try to follow these conventions in new posts!