Function lcm_many

pub fn lcm_many(elems: &[u64]) -> u64

Finds the LCM (Least Common Multiple) for an array of elements.

Examples

use ads_rs::prelude::v1::math::lcm_many;

let res0 = lcm_many(&[42, 8, 144]);
let res1 = lcm_many(&[89, 144, 233, 377, 610]);
let res2 = lcm_many(&[25, 105, 235, 100]);

assert_eq!(24192, res0);
assert_eq!(686719856160, res1);
assert_eq!(12337500, res2);

Corner cases

• LCM of an empty array equals 0.
• LCM of a single element array equals that element.

use ads_rs::prelude::v1::math::lcm_many;

let res0 = lcm_many(&[]);
let res1 = lcm_many(&[25]);

assert_eq!(0, res0);
assert_eq!(25, res1);

Implementation details

• Stein’s algorithm is used to find GCD (from gcd_many).
• Time complexity: O(K * N²) where:
  • N - bits count in the biggest number.
  • K - number’s count