C program to find LCM and GCD of two numbers

C program to find LCM and GCD of two numbers - Source code

     
                
  /*
C program to find the LCM and GCD of two integers
 */

#include <stdio.h>

void main()
{
    int num1, num2, gcd, lcm, rem, numerator, denominator;

    printf("Enter the two numbers\n");
    scanf("%d %d", &num1, &num2);
    if (num1 > num2)
    {
        numerator = num1;
        denominator = num2;
    }
    else
    {
        numerator = num2;
        denominator = num1;
    }
    rem = numerator % denominator;
    while (rem != 0)
    {
        numerator   = denominator;
        denominator = rem;
        rem   = numerator % denominator;
    }
    gcd = denominator;
    lcm = num1 * num2 / gcd;
    printf("GCD of %d and %d = %d\n", num1, num2, gcd);
    printf("LCM of %d and %d = %d\n", num1, num2, lcm);
}
     
      

Program Output

Case 1:

Enter the two numbers
20
5
GCD of 20 and 5 = 5
LCM of 20 and 5 = 20

Case 2:

Enter the two numbers
56
8
GCD of 56 and 8 = 8
LCM of 56 and 8 = 56

Program Explanation

1. This program compute the GCD of two numbers using the very well known Euclid's algorithm. To calculate the LCM of two numbers , product of two numbers is divided by the calculated GCD.

2. The largest of the two numbers is assigned to variable numerator while the smaller one to denominator.

3. Remainder is calculated by dividing the numerator by denominator. Denominator becomes the new numerator and remainder becomes the new denominator. Again, remainder is calculated with this new numerator and denominator.

4. This process is repeated until remainder becomes zero. The value of GCD is the last calculated denominator.

5. The LCM is calculated by dividing the product of two numbers with the calculated GCD.