Greater Common Divisor Algorithm

The Greater Common Divisor (GCD) Algorithm, also known as the Euclidean Algorithm, is a widely-used method for finding the greatest common divisor of two integers - the largest number that divides both numbers without leaving a remainder. This algorithm plays an essential role in number theory and has numerous applications in fields such as cryptography, computer science, and mathematics. The GCD Algorithm is based on the principle that the greatest common divisor of two numbers does not change if the smaller number is subtracted from the larger number. Repeatedly applying this step eventually leads to a pair of numbers where one of them is zero, and the other is the greatest common divisor. The Euclidean Algorithm can be implemented using either an iterative or recursive approach. In the iterative method, the algorithm starts by dividing the larger number by the smaller number and taking the remainder. Then, the smaller number becomes the divisor, and the remainder becomes the dividend for the next iteration. This process continues until the remainder is zero, at which point the last non-zero remainder is the greatest common divisor. In the recursive approach, the algorithm follows the same logic but is implemented using a function that calls itself with updated dividend and divisor values until the base case of a zero remainder is reached. Both methods are efficient and reliable ways of finding the greatest common divisor of two integers, and their simplicity makes them popular choices for programming and computation tasks involving number theory.
package Mathematics

object GreaterCommonDivisor {

	/**
	    * Method returns the Greatest Common Divisor of two numbers n, m
	    *
	    * @param num1, num2
    	    * @return
    	*/

	def gcd(num1: Long, num2: Long): Long = {
    		if (num2 == 0) num1
    		else gcd(num2, num1 % num2)
  	}
  
}

LANGUAGE:

DARK MODE: