Find GCD of two numbers

Given two numbers A and B, the task is to calculate GCD of A and B.

Examples:

Input : A = 4, B = 6
Output : 2

Input : A = 5, B = 10
Output : 5

GCD (Greatest Common Divisor) of two number is the largest number that divides both of them.
A simple solution to find GCD of two numbers is to factorise both numbers and multiply common factors.
An efficient solution is to use Basic Euclidean Algorithm for GCD, which is based on the principle that GCD of two number does not changes if the large number is replaced by its difference with smaller number. So if we keep replacing larger number by its difference with the smaller number, we will end up with the GCD of original numbers.

Below is the implementation of above approach:

// Scala program to find
// GCD of two numbers 

// Creating Object
object W3Colleges {

  // Function to calculate 
  // GCD of two numbers
  def gcd(A: Int, B: Int): Int = { 
    // If A is 0, return B
    if (A == 0) 
      B
    // If B is 0, return A
    else if (B == 0) 
      A
    // If A is equal to B, return A or B
    else if (A == B) 
      A
    // If A is greater, call gcd recursively
    else if (A > B) 
      gcd(A - B, B)
    else 
      gcd(A, B - A)
  } 
  
  // Driver Code 
  def main(args: Array[String]): Unit = { 
    val A = 4
    val B = 6
    
    println(s"The GCD of $A and $B is: ${gcd(A, B)}") 
  } 
}

Output:

More efficient approach:
Instead of replacing larger number by its difference with smaller number, we can replace the larger of the two numbers by its remainder when divided by smaller of the two numbers, to get the same result.
The algorithm stops, when we get remainder as 0.

Below is the implementation of above approach:

// Scala program to calculate
// GCD of two numbers 

// Creating Object
object W3Colleges {

  // Function to calculate 
  // GCD of two numbers
  def gcd(A: Int, B: Int): Int = { 
    if (B == 0) 
      A
    else 
      gcd(B, A % B)
  } 
  
  // Driver Code 
  def main(args: Array[String]): Unit = { 
    val A = 4
    val B = 6
    
    println(s"The GCD of $A and $B is: ${gcd(A, B)}") 
  } 
}

Output: