DEV Community

Cover image for Euclid's GCD Algorithm
Scott Gordon
Scott Gordon

Posted on

Euclid's GCD Algorithm

#   Euclid's algorith states that starting with values m and n, if we were
#   to repeatedly apply the formula: n, m = m, n%M until m is 0.
#   This program finds the GCD of two numbers using this formula.
# by: Scott Gordon

def gcd(n, m):
    while m != 0:
        n, m = m, n % m
    return n

def main():

    print("Welcome to Euclid's GCD algorithm\n")
    num1, num2= input("Enter two natural numbers (n1, n2): ").split(",")

    print(f"The GCD of {num1} and {num2} is {gcd(int(num1),int(num2))}")

if __name__ == '__main__':
Enter fullscreen mode Exit fullscreen mode

Discussion (0)