Euclidean algorithm.

Euclidean method GCD use case.


The Euclidean algorithm in mathematics is an efficient method for computing the greatest common divisor (GCD) of two integers. The highest common factor HCF or greatest common divisor GCD of two numbers is the largest positive integer that divides the two given numbers. The Euclidean algorithmIn is named after the ancient Greek mathematician Euclid (300 BC).

Euclidean algorithm.



It uses step-by-step procedure for performing a calculation according to well-defined rules and is one of the oldest known math algorithms in use. It is used to reduce fractions to their simplest form, and sometimes used as a part of many other math and cryptographic calculations. The main principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. Since this replacement reduces the larger number, repeating this process gives at the end smaller pairs of numbers until the two numbers become equal.


Euclidean algorithm Python code:




def gcd(a, b):
    if a == 0 :
        return b
     
    return gcd(b%a, a)
 
a = 25
b = 55
print("gcd(", a , "," , b, ") = ", gcd(a, b))
 
a = 21
b = 42
print("gcd(", a , "," , b, ") = ", gcd(a, b))
 
a = 111
b = 2
print("gcd(", a , "," , b, ") = ", gcd(a, b))

OUT: gcd( 25 , 55 ) = 5
gcd( 21 , 42 ) = 21
gcd( 111 , 2 ) = 1





See also related topics: