Project Euler in Clojure – Problem 7

In trying to learn Clojure and wrap my head around good functional programming, and hoping to learn more idiomatic Clojure, I have started working through the Project Euler problems. In doing this, I have also setup a repository on github.com to keep track of my progress, which can be found at https://github.com/stevenproctor/project-euler-clojure.  My approach to Problem 6 can be found here.

Problem 7 of Project Euler is described as:

What is the 10 001st prime number?
(defn is-prime? [n]
  (cond (<= n 1) false
        (= n 2) true
        :else (loop [f 2]
                (cond (zero? (rem n f)) false
                      (> f (Math/sqrt n)) true
                      :else (recur (inc f))))))

(defn problem7
  ([] (problem7 10001))
  ([n] (first (skip-n (dec n) (filter is-prime? (iterate inc 1))))))

The is-prime? function check to see if the number is prime by checking if any of the numbers from 2 to the square root of the number is a divisor of the number.

The problem7 function is finds the n-th number in the sequence by skiping n-1 items, and then taking the first item of that sequence. This was before a previous post in which someone pointed out that the drop function was available instead of my home rolled skip-n function, so that can be replaced on the update.

Again, I would love comments and suggestions on my solution to this problem, and if there are tweaks to make it more Clojure-ish.

**Update**
My solution to Problem 8 has been posted.

–Proctor

Advertisements

, ,

  1. #1 by Arcane Sentiment on June 7, 2012 - 19:38

    The loop can be written more concisely with some or not-any? and range. You might also try dividing only by prime factors instead of all integers; this is a good exercise in recursive lazy data.

    The is- prefix is not necessary, since it means the same thing as the ? suffix.

    You probably want nth instead of (first (drop ...)).

    problem7 is an awkward name. Unless you want to name all your solutions like this, how about a descriptive name like nth-prime instead? (However, I probably wouldn’t bother creating this function at all — I’d just write the expression to get the 10001st prime.)

    • #2 by Proctor on June 7, 2012 - 20:37

      So you are suggestion something along the lines of:

      (defn factor-of? [f n] (zero? (rem n f)))
      
      (defn prime? [n] (not-any? #(factor-of? % n) (range 2 n)))
      

      That does come across much more elegant and simple.

      And for nth, as soon as I read your comment, it hit me as obvious.

      Thanks for your feedback,
      –Proctor

      • #3 by Arcane Sentiment on June 8, 2012 - 13:59

        Yes. Or, more efficiently:

        (defn prime? [n] (not-any? #(factor-of? % n)
                                   (take-while #(<= (* % %) n) primes)))

        where primes is the infinite sequence of primes.

  1. Project Euler in Clojure – Problem 6 « Proctor It
  2. Project Euler in Clojure – Problem 8 « Proctor It

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: