greatest common divisor Algorithm
The greatest common divisor (GCD) algorithm is a mathematical procedure used to determine the largest positive integer that divides two or more numbers without leaving a remainder. It is an essential concept in number theory and has applications in various fields such as cryptography, computer science, and engineering. The most famous and widely-used GCD algorithm is the Euclidean algorithm, which dates back to the ancient Greek mathematician Euclid's work, "Elements," written around 300 BCE. The algorithm is based on the principle that the GCD of two numbers is the same as the GCD of the smaller number and the remainder when the larger number is divided by the smaller number.
To illustrate the Euclidean algorithm, let's consider two integers a and b, where a > b > 0. The algorithm involves dividing a by b and finding the remainder, r. Then, replace a with b and b with r, and repeat the process until the remainder becomes zero. At this point, the divisor (b) is the GCD of a and b. This method can be implemented using either recursion or iteration, and it can be extended to find the GCD of more than two numbers by applying the algorithm pairwise. The Euclidean algorithm is efficient and fast, making it suitable for use in complex calculations and real-world applications.
"""
Greatest Common Divisor.
Wikipedia reference: https://en.wikipedia.org/wiki/Greatest_common_divisor
"""
def greatest_common_divisor(a, b):
"""
Calculate Greatest Common Divisor (GCD).
>>> greatest_common_divisor(24, 40)
8
>>> greatest_common_divisor(1, 1)
1
>>> greatest_common_divisor(1, 800)
1
>>> greatest_common_divisor(11, 37)
1
>>> greatest_common_divisor(3, 5)
1
>>> greatest_common_divisor(16, 4)
4
"""
return b if a == 0 else greatest_common_divisor(b % a, a)
"""
Below method is more memory efficient because it does not use the stack (chunk of memory).
While above method is good, uses more memory for huge numbers because of the recursive calls
required to calculate the greatest common divisor.
"""
def gcd_by_iterative(x, y):
"""
>>> gcd_by_iterative(24, 40)
8
>>> greatest_common_divisor(24, 40) == gcd_by_iterative(24, 40)
True
"""
while y: # --> when y=0 then loop will terminate and return x as final GCD.
x, y = y, x % y
return x
def main():
"""Call Greatest Common Divisor function."""
try:
nums = input("Enter two integers separated by comma (,): ").split(",")
num_1 = int(nums[0])
num_2 = int(nums[1])
print(
f"greatest_common_divisor({num_1}, {num_2}) = {greatest_common_divisor(num_1, num_2)}"
)
print(f"By iterative gcd({num_1}, {num_2}) = {gcd_by_iterative(num_1, num_2)}")
except (IndexError, UnboundLocalError, ValueError):
print("Wrong input")
if __name__ == "__main__":
main()
