Problem Description, from Project Euler
What is the n-th prime number?
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:
; //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:
(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) )