Least Common Multiple

and program in Rust to calculate it using Euclidean algorithm.

What is Least Common Multiple ( LCM )

Least Common Multiple of two natural numbers is the smallest natural number that is divisible by both the numbers.

Lowest Common denominator is used for rational numbers, and it is LCM of denominators of both numbers.

For Example : LCM of 100 and 75 is 300

Naive Approach

Let us suppose we have to find Least Common Multiple ( LCM ) of 2 numbers, a and b.

The naive or brute force approach would be to traverse all the numbers from max(a, b) to a × b and find if it is divisible by both a and b. If yes, print the number and return.

We will not write its code, because it is very clumsy.

Time Complexity : O( a × b )
Space Complexity : O( 1 )

Efficient Euclidean algorithm

We know that, product of 2 numbers is equal to product of their GCD and LCM. Mathematically,

We already saw How To find HCF of 2 numbers using Euclidean Algorithm Here. We will use this function to find LCM of 2 numbers.

So,

Function using this approach is

// Find GCD
fn gcd(mut a:usize, mut b:usize) -> usize{
    if a==b { return a; }
    if b > a {
        let temp = a;
        a = b;
        b = temp;
    }
    while b>0 {
        let temp = a;
        a = b;
        b = temp%b;
    }
    return a;
}

fn lcm(a:usize, b:usize) -> usize{
    // LCM = a*b / gcd
    return a*(b/gcd(a,b));
}

With driver code

use std::io::stdin;

// Read Input

fn take_vector() -> Vec<usize> {
    let mut input = String::new();
    stdin().read_line(&mut input).unwrap();
    let arr: Vec<usize> = input.trim()
        .split_whitespace().map(|x| x.parse().unwrap()).collect();
    return arr;
}

// Magic Starts here

// Find GCD
fn gcd(mut a:usize, mut b:usize) -> usize{
    if a==b { return a; }
    if b > a {
        let temp = a;
        a = b;
        b = temp;
    }
    while b>0 {
        let temp = a;
        a = b;
        b = temp%b;
    }
    return a;
}

fn lcm(a:usize, b:usize) -> usize{
    // LCM = a*b / gcd
    return a * (b/gcd(a,b));
}

// Driver Code

pub fn main() {
    let numbers = take_vector();
    println!("{}", lcm(numbers[0], numbers[1]));
}

Input

210 150

Output

1050

Time Complexity : O( log(min (a, b)) )
Space Complexity : O( 1 )

Conclusion

Least Common Multiple of two natural numbers is the smallest natural number that is divisible by both the numbers. In this article, we made a program to compute Least Common Multiple (LCM) of two numbers in Logarithmic Time Complexity using Euclidean algorithm in Rust.

Here is optimized function for easy access.

fn gcd(mut a:usize, mut b:usize) -> usize{
    if a==b { return a; }
    if b > a { let temp = a; a = b; b = temp; }
    while b>0 { let temp = a; a = b; b = temp%b; }
    return a;
}

fn lcm(a:usize, b:usize) -> usize{
    return a*(b/gcd(a,b));
}

Thank You