find the least common multiple of a list of numbers in rust

To find the least common multiple (LCM) of a list of numbers in Rust, we can use the std::ops::Mul trait and the Euclidean algorithm.

The Euclidean algorithm works by repeatedly finding the greatest common divisor (GCD) of two numbers and dividing the larger number by the GCD. The algorithm terminates when the GCD is 1, at which point the remaining numbers are pairwise coprime, and their product is the LCM.

Here is some Rust code that implements this algorithm:

main.rs
use std::ops::Mul;

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let r = a % b;
        a = b;
        b = r;
    }
    a
}

fn lcm(numbers: &[u64]) -> Option<u64> {
    if numbers.is_empty() {
        return None;
    }
    let mut result = numbers[0];
    for &n in &numbers[1..] {
        if n == 0 {
            return None;
        }
        result = match result.checked_mul(n) {
            Some(p) => p / gcd(result, n),
            None => return None,
        };
    }
    Some(result)
}
520 chars
28 lines

The gcd function computes the GCD of two numbers using the Euclidean algorithm. The lcm function takes a slice of u64 numbers, and iteratively multiplies the current LCM by the next number, divided by their GCD, until all numbers are processed. The checked_mul method checks for integer overflow and returns None if it occurs.

Here is an example usage of the lcm function:

main.rs
fn main() {
    let numbers = [3, 5, 7, 11];
    match lcm(&numbers) {
        Some(result) => println!("LCM: {}", result),
        None => println!("Invalid input"),
    };
}
176 chars
8 lines

This will output LCM: 1155, which is the least common multiple of the input list [3, 5, 7, 11].