Problem 3: Prime Factor

13 10 2009

Find the largest prime factor of a composite number

The brute force method would be to find all the prime factors and choose the largest, a better algorithm is this one.

(defn divides? [n x]
    (zero? (mod n x)))

(defn largest-prime-divisor [n]
    (loop [x 2 m n]
	    (= x m) x
	    (divides? m x) (recur x (/ m x))
	    :else (recur (inc x) m))))

Clojure’s syntax takes a while getting used to but now I find it quite easy to express an algorithm in it. Lets trace what happens with a small value

(largest-prime-divisor 100)
(loop 2 100)
(loop 2 50)
(loop 2 25)
(loop 3 25)
(loop 4 25)
(loop 5 25)
(loop 5 5)
=> 5



Leave a Reply

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

You are commenting using your 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: