Least Common Multiple on Wikipedia.
How well can the prime factorization method be expressed in F#? This is my first solution and just for fun:
open System
/// Generate sequence of all integer primes
let primes =
let isPrime x =
let rec test = function
| 1 -> true
| n -> if x % n = 0 then false else test (n-1)
test (x/2)
seq {
yield! [1;2;3;5;7]
for n in 11..2..Int32.MaxValue do
if isPrime n then yield n
done
}
/// Compute prime factors
/// <returns>
/// Sequence of prime number powers (x^y) as tuple of (x,y)
/// </returns>
let primefactors x =
/// Compute prime factor
let primefactor x =
primes
|> Seq.skip 1
|> Seq.takeWhile (fun prime -> prime <= x)
|> Seq.tryFind (fun prime -> (x % prime) = 0)
/// Compute list of prime factors
let rec fold acc x =
match primefactor x with
| Some factor -> fold (factor::acc) (x/factor)
| None -> acc
fold [] x
|> Seq.countBy (fun x -> x)
/// Compute lowest common multiple
let lcm xs =
xs // {8;9;21}
|> Seq.map primefactors // {{2^3};{3^2};{3^1;7^1}}
|> Seq.concat // {2^3;3^2;3^1;7^1}
|> Seq.groupBy (fun (x,y) -> x) // {{2;{2^3}};{3;{3^1;3^2}};{7;{7^1}}}
|> Seq.map (fun (x,xys) ->
x, // 3
xys // {3^1;3^2}
|> Seq.map snd // {1;2}
|> Seq.max // 2
) // {2^3;3^2;7^1}
|> Seq.map (fun (x,y) ->
pown x y // {8;9;7}
)
|> Seq.reduce (*) // 504
do lcm [8;9;21] |> printf "%d" // yields 504