Problem 5: Lowest Common Multiple

14 10 2009

Find the smallest number divisible by each of the numbers 1 to 20

The requirement is to find the Lowest Common Multiple (LCM)of the numbers 1 to 20

We can very easily find the LCM using the  Greatest Common Divisor (GCD) using the formula

lcm(x, y) = (x * y) / gcd(x, y)

A very fast method to calculate GCD is using Euclid’s algorithm

gcd(x, y) = gcd(y, x mod y)

Implementing this in Clojure

(defn gcd [x y]
    (cond
	(zero? x) y
	(zero? y) x
	:else (recur y (mod x y))))

(defn lcm [x y]
    (/ (* x y) (gcd x y)))

(reduce lcm (range 1 21))

gcd calculates the greatest common divisor of 2 integers

(gcd 6 8 )
=> 2

lcm calculates the lowest common multiple of 2 integers

(lcm 6 8 )
=> 24
Advertisements

Actions

Information

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: