Books I Like

Sunday, November 1, 2009

Solving Project Euler Problem #7 in Ruby, Clojure

Problem Statement :
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution :

This works on Ruby 1.9+. Here we have taken advantage of the method discusses here to create Lazy enumerator in Ruby. I started looking for the ruby equivalent as the clojure code becomes so easy to deal with using the lazy sequences.

require "mathn"
infinity = 1.0/0.0
module Enumerable
def lazy_select do |yielder|
each do |obj|
yielder.yield(obj) if yield(obj)

p (1..infinity).lazy_select { |v| }.take(10001).last

The clojure code is as follows :
Here we have added one optimization (Any prime number after 2 and 3, when divided by 6, leaves the remainder 5 or 1).

(defn sqrt [x]
(int (Math/sqrt x)))

(defn get-smallest-prime-factor [n]
(loop [n n d 2]
(cond (> d (sqrt n)) n
(= n d) n
(= 0 (rem n d)) d
true (recur n (inc d)))))

(def get-nth-prime
(lazy-cat '(2 3)
#(= % (get-smallest-prime-factor %))
#(or (= 1 (rem % 6)) (= 5 (rem % 6)))
(take-nth 2 (iterate inc 3))))))

(println (nth get-nth-prime 10000))

Here is another cheat, if you have installed the clojure contrib library.

(use 'clojure.contrib.lazy-seqs)
(println (nth primes 10000))

1 comment:

Jeff said...

I solved this a little differently - used lazy seq, no optimization, just use the earlier list of known primes as the list of potential divisors.

(def prime?)

(def primes
(lazy-seq (concat [2 3 5] (filter prime? (iterate #(+ 2 %) 7)))))

(defn prime? [mynum]
(every? #(not (integer? (/ mynum %)))
(take (.intValue (. Math floor (. Math sqrt mynum))) (rest primes))))

Get at Amazon