This one was pretty easy. We only need to test i against 11 to 20 since the numbers in that range are themselves divisible by those in 1 to 10. Also, a lower bound for i is the product of all primes in 1 to 20.
let problem5a = let rec find i = if {11..20} |> Seq.forall (fun d -> i % d = 0) then i else find (i + 1) find (2*3*5*7*11*13*17*19)
This can be done 50,000 times faster in F#.
ReplyDeleteBridging the gap between 9,699,690 (the product of the primes under 20) and 232,792,560 (the correct answer) by looping 223 million times is guaranteed to run slowly.
Clearly we need another approach. The best way I think is to get the LCM of consecutive pairs of numbers between 11 and 20, using their GCD to eliminate shared factors, e.g.
let rec gcd x y =
... if y = 0 then x
... else gcd y (x%y)
let lcm x y = x*y / (gcd x y)
[11 .. 20] |> List.reduce lcm
This takes 1 ms on my PC rather than 50 seconds.