ads_rs::v1::math

Function lcm

Source 
pub fn lcm(lhs: u64, rhs: u64) -> u64
Expand description

Finds an LCM (Least Common Multiple) for a pair of numbers.

§Examples

use ads_rs::prelude::v1::math::lcm;

let res0 = lcm(42, 144);
let res1 = lcm(377, 610);
let res2 = lcm(105, 25);

assert_eq!(1008, res0);
assert_eq!(229970, res1);
assert_eq!(525, res2);

§Corner case

LCM of both zero numbers equals 0.

use ads_rs::prelude::v1::math::lcm;

let res = lcm(0, 0);

assert_eq!(0, res);

§Implementation details

  • Stein’s algorithm used (from gcd_many).
  • Time complexity: O(N2) where N - number of bits in the biggest number.