// algorithm from http://en.wikipedia.org/wiki/Least_common_multiple
func lcm(a, b uint64) uint64 {
return (a / gcd(a, b)) * b
}
// copied from C in http://en.wikipedia.org/wiki/Binary_GCD_algorithm
func gcd(u, v uint64) uint64 {
var shift uint
switch {
case u == 0:
return v
case v == 0:
return u
}
for shift = 0; ((u | v) & 1) == 0; shift++ {
u >>= 1
v >>= 1
}
for (u & 1) == 0 {
u >>= 1
}
for {
for (v & 1) == 0 {
v >>= 1
}
if u > v {
t := v
v = u
u = t
}
v = v - u
if v == 0 {
break
}
}
return u << shift
}