in Programming

Project Euler Problem 7 Solution: Clojure

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:

; //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)
)


  1. 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!

Comments are closed.

  • Readers who shared this
  • wifi tv
  • Thank you!