by Dinesh Thakur Category: Control Structures

The Greatest Common Divisor of two positive integers can be calculated iteratively by the following formula known as Euclid's algorithm. You can see that this is a recursive definition with GCD(m,n) defined in terms of GCD(n,m%n).

                GCD(m,n)           = GCD (n,m)                      if n>m

                                              =m,                                      if n=0

                                              = GCD(n, m%n)                otherwise

We can also compute the Least Common Multiple of the two integers by using the following relation between the GCD and the LCM.

                LCM * GCD = m * n

The C program given below uses Euclid's algorithm to compute the GCD and the LCM of two integers.

#include<stdio.h>

#include<stdlib.h>
int main()
{
   long n, m, temp, big, small;
   long gcd , lcm;
   clrscr();
   printf("\n Enter two integers ");
   scanf("%ld %ld", &n , &m);
    if(n==0||m==0)
    {
               printf("\n ERROR: one of the values equals O.");
               exit(0);
    }
   big=n;
   small=m;
     while(small!=0)
     {
               if(big<small)
               {
                  temp=big;
                  big=small;
                  small=temp;
               }
                         printf("\n %ld %ld", big , small);
                         temp=big%small;
                         big=small;
                         small=temp;
     }
             gcd=big;
             lcm=m*(n/big);
             printf("\n\n GCD of %ld and %ld is %ld\n", n , m, gcd);
             printf("\n LCM of %ld and %ld is %ld\n", n , m , lcm);
             return 0;
}

Euclids algorithm



About Dinesh Thakur

Dinesh ThakurDinesh Thakur holds an B.SC (Computer Science), MCSE, MCDBA, CCNA, CCNP, A+, SCJP certifications. Dinesh authors the hugely popular blog. Where he writes how-to guides around Computer fundamental , computer software, Computer programming, and web apps. For any type of query or something that you think is missing, please feel free to Contact us.



Search Content







Popular Article