[Algorithm] - Euclid's Algorithm to find GCD of two numbers, with an example

This post will tell you in detail about "Euclid's Algorithm to find GCD of two numbers with an example"

This algorithm calculates the Greatest common divisor (GCD) of two input numbers. This algorithm uses recursive method of problem solving.

CODE:

ALGORITHM Euclid(m,n)
{
     if(n=0)
          return m
     else
      {
               R=m mod n
               m=n
               n=R
               return Euclid(m,n)
      }
}

Recursive technique:

 GCD (m , n ) = GCD ( n , m mod n )

The steps are as follows,

To find GCD of two numbers m and n, 
step 1: If n=0, return the value of m as the answer. Otherwise, proceed to step 2.
step 2: Divide m by n and assign the value of the reminder to R.
step 3: Assign value of n to m, and value of R to n. Go to step 1.


Example:
Finding GCD of two 60 and 24: 
= > GCD(60,24)

Recursive calls

1.Value of n=24 (not zero), 
   R= m mod n = 60%24 = 12.
   m=24
   n=12

2.Value of n=12 (not zero)
   R= m mod n = 24%12= 0.
   m=12
   n=0

3.Value of n=0 (Zero)
   Return value of m as the answer. I.e., m=12 is the answer.



The required GCD of 60 and 24 is 12.




I think this problem can answer the question "Explain Euclid's algorithm with an example" or "What is Euclid's algorithm and how it can be used to check GCD of two numbers". Mainly for VTU Students. :P


Tags: Euclid,Algorithm,GCD,ADA,DAA

Author : Anonymous

He is a simple passionate tech freak who himself is an engineering student at Canara Engineering college. He likes App Development, Web designing, Blogging, Youtubing, Debugging and also is a CodeGeek!

Sharing is sexy!

Related Articles