在项目euler#5中输入overflow

Question

我正在尝试解决项目euler#5:

2520是可以除以1到10中的每个数字而没有任何余数的最小数字.

可以被1到20的所有数字整除的最小正数是多少？

这是我的代码:

open System

let rec gcd a b =
    match b with
        | x when x = 0 -> a
        | _ -> gcd b (a % b)

let lcm a b = (a * b) / (gcd a b)        
let result = Seq.fold lcm 1 [1..20]

[<EntryPoint>]
let main(args : string[]) =
    printfn "result = %d" result 
    0

它可以正常使用数字[1..19],但是数字[1..20]得到了错误的结果.我试图找出错误的原因,并发现:

$ Seq.fold lcm 1 [1..19]
232792560 // right
$ lcm 232792560 20
18044195 // wrong

看起来类型溢出.我该如何修复错误？

Answer 1

使用BigInt,一个不会溢出的整数类型.如果您要更换0用0I(该I后缀用于BigInt中文字)gcd,那么这两个gcd和lcm将infered一起工作BigInts,而不是int秒.