A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

C program to find LCM and GCD of two numbers


Problem Description


This C program calculates the LCM and GCD of two given integer numbers. LCM (Least Common Multiple) of two numbers is the smallest number which can be divided by both numbers. For example LCM of 15 and 20 is 60 and LCM of 5 and 7 is 35.
The HCF or GCD of two integers is the largest integer that can exactly divide both numbers (without a remainder). 


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.