GCD, LCM

gcd(x, y) returns the greatest common divisor (GCD) of x and y.
lcm(x, y) returns the least common multiple (LCM) of x and y.

gcd is implemented using Euclidean algorithm, whose time complexity is \(O( \log _{\phi} x )\) where \(\phi\) is a golden ratio.

Example

fn main() {
let (x, y) = (10, 25);

let g = gcd(x, y);
println!("{}", g); // 5

let l = lcm(x, y);
println!("{}", l); // 50
}

fn gcd(x: u64, y: u64) -> u64 {
   if y == 0 {
       x
   } else {
       gcd(y, x % y)
   }
}

fn lcm(x: u64, y: u64) -> u64 {
   x / gcd(x, y) * y
}

Code

fn gcd<T>(x: T, y: T) -> T
where T: Copy + PartialEq + PartialOrd + Rem<Output = T> + From<u8> {
	if y == 0.into() {
		x
	} else {
		let v = x % y;
		gcd(y, v)
	}
}

fn lcm<T>(x: T, y: T) -> T
where T: Copy + PartialEq + PartialOrd + Rem<Output = T> + Div<Output = T> + Mul<Output = T> + From<u8> {
	x / gcd(x, y) * y
}

Last modified on 231203.