Mumbai University > Information Technology > Sem 3 > Data structure and algorithm analysis

Marks: 5M

Year: Dec 2015, May 2016

Euclid’s algorithm is used for computing the greatest common divisor. The greatest common divisor (gcd) of two integers is the largest integer that divides both. Thus gcd(50,15)= 5.The algorithm below computes greatest common divisor.

This algorithm assumes M>= N. The algorithm works by continually computing remainders until 0 is reached. The last nonzero remainder is the answer. Thus, if M =1,989 and N =1,590, then the sequence of remainders is 399, 393, 6, 3, 0. Therefore, gcd (1989, 1590) =3.