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

Enumerator.new do |yielder|

each do |obj|

yielder.yield(obj) if yield(obj)

end

end

end

end

p (1..infinity).lazy_select { |v| v.prime? }.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)

(filter

#(= % (get-smallest-prime-factor %))

(filter

#(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:

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

Post a Comment