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.


int main()
   long n, m, temp, big, small;
   long gcd , lcm;
   printf("\n Enter two integers ");
   scanf("%ld %ld", &n , &m);
               printf("\n ERROR: one of the values equals O.");
                         printf("\n %ld %ld", big , small);
             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.C.A, 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.

Related Articles