GCD or HCF of two numbers

and program in Rust to calculate it using Euclidean algorithm.

What is GCD or HCF

Greatest Common Divisor ( GCD ) or Highest Common Factor ( HCF ) of two natural numbers is the largest natural number that divides both numbers.

We can also say it is the largest natural number that is factor of both numbers.

For Example : GCD of 100 and 75 is 25

Naive Approach

Let us suppose we have to find gcd or hcf of 2 numbers, a and b.

Naive or brute force approach is to traverse all the numbers from 1 to min(a, b), and check if the number divides both numbers. Function using this approach is

fn gcd(a:usize, b:usize) -> usize{
    // Initialize ans, or answer and limit
    let mut ans:usize = 1;
    let limit = min(a,b);

    // Loop from 2 to limit, both inclusive
    for i in 2..(limit+1) {
        // Check if both a and b are divisible
        if a%i == 0 && b%i == 0 {
            ans = i;
        }
    }
    return ans;
}

Program With driver code

use std::cmp::min;
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

fn gcd(a:usize, b:usize) -> usize{
    // Initialize ans, or answer and limit
    let mut ans:usize = 1;
    let limit = min(a,b);

    // Loop from 2 to limit, both inclusive
    for i in 2..(limit+1) {
        // Check if both a and b are divisible
        if a%i == 0 && b%i == 0 {
            ans = i;
        }
    }
    return ans;
}

// Driver Code

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

Input

210 150

Output

30

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

Efficient Euclidean algorithm

We can find the gcd of 2 numbers using Euclidean algorithm in logarithmic time complexity

Refer Wikipedia

In simple words, let us suppose that we have to find gcd of 2 distinct numbers, a and b, such that a > b.

• If a%b == 0, then obviously b is the gcd.
• If a%b != 0, then gcd must divide both b and a%b ( from Euclidean algorithm or even general observation ). So, we can now find gcd of b and a%b, which will be the answer.

Also, clearly, b > a%b.

Function using this approach is

fn gcd(mut a:usize, mut b:usize) -> usize{
    // If equal, return any of them
    if a==b {
        return a;
    }

    // Swap a with b, if b is greater than a
    if b > a {
        std::mem::swap(&mut a, &mut b);
    }

    while b>0 {
        // This is the trickiest part
        // We swap a with b, and b with a%b, till b becomes 0
        let temp = a;
        a = b;
        b = temp%b;
    }

    // Now, a%b = 0, hence return it
    return a;
}

Use the same driver code.

Input

210 150

Output

30

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

Conclusion

Greatest Common Divisor ( GCD ) or Highest Common Factor ( HCF ) of two natural numbers is the largest natural number that divides both numbers. In this article, we made a program to compute GCD or HCF in Logarithmic Time Complexity using Euclidean algorithm.

Here is the optimized function for easy access

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

Thank You