TheAlgorithms-Python

1
"""
2
Greatest Common Divisor.
3

4
Wikipedia reference: https://en.wikipedia.org/wiki/Greatest_common_divisor
5

6
gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b) by definition of divisibility
7
"""
8

9

10
def greatest_common_divisor(a: int, b: int) -> int:
11
    """
12
    Calculate Greatest Common Divisor (GCD).
13
    >>> greatest_common_divisor(24, 40)
14
    8
15
    >>> greatest_common_divisor(1, 1)
16
    1
17
    >>> greatest_common_divisor(1, 800)
18
    1
19
    >>> greatest_common_divisor(11, 37)
20
    1
21
    >>> greatest_common_divisor(3, 5)
22
    1
23
    >>> greatest_common_divisor(16, 4)
24
    4
25
    >>> greatest_common_divisor(-3, 9)
26
    3
27
    >>> greatest_common_divisor(9, -3)
28
    3
29
    >>> greatest_common_divisor(3, -9)
30
    3
31
    >>> greatest_common_divisor(-3, -9)
32
    3
33
    """
34
    return abs(b) if a == 0 else greatest_common_divisor(b % a, a)
35

36

37
def gcd_by_iterative(x: int, y: int) -> int:
38
    """
39
    Below method is more memory efficient because it does not create additional
40
    stack frames for recursive functions calls (as done in the above method).
41
    >>> gcd_by_iterative(24, 40)
42
    8
43
    >>> greatest_common_divisor(24, 40) == gcd_by_iterative(24, 40)
44
    True
45
    >>> gcd_by_iterative(-3, -9)
46
    3
47
    >>> gcd_by_iterative(3, -9)
48
    3
49
    >>> gcd_by_iterative(1, -800)
50
    1
51
    >>> gcd_by_iterative(11, 37)
52
    1
53
    """
54
    while y:  # --> when y=0 then loop will terminate and return x as final GCD.
55
        x, y = y, x % y
56
    return abs(x)
57

58

59
def main():
60
    """
61
    Call Greatest Common Divisor function.
62
    """
63
    try:
64
        nums = input("Enter two integers separated by comma (,): ").split(",")
65
        num_1 = int(nums[0])
66
        num_2 = int(nums[1])
67
        print(
68
            f"greatest_common_divisor({num_1}, {num_2}) = "
69
            f"{greatest_common_divisor(num_1, num_2)}"
70
        )
71
        print(f"By iterative gcd({num_1}, {num_2}) = {gcd_by_iterative(num_1, num_2)}")
72
    except (IndexError, UnboundLocalError, ValueError):
73
        print("Wrong input")
74

75

76
if __name__ == "__main__":
77
    main()
78