Project Euler in F#: Problem 5

What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

module Problem5 =
    //lcm = product / gcd; could get rid of the % op by using Euclid's
    let rec gcd n m =
        if m = 0 then n
        else gcd m (n%m)

    let lcm n m = n / (gcd n m) * m //we get an overflow if we don't divide first (or use a long)
    let ans = {1..2000} |> Seq.reduce lcm

I thought this was a pretty boring problem, from a learning-F# point of view, but, once again, Dustin managed to teach me something new: F#’s bigint type has a built in gcd function.

Advertisements
Project Euler in F#: Problem 5

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