C Program to find GCD(HCF) and LCM using euclid algorithm

For a better understanding of this C program example, we always recommend you to learn the basic topics of C programming listed below:

What is GCD or HCF?

This is a C program to find the GCD of two numbers. GCD of two numbers means the biggest number which divides both the numbers. Suppose we have two numbers 36 and 60 then the gcd is.

How GCD or HCF calculated in the C program?

This C program uses Euclid's algorithm to find the GCD(HCF) and lcm of the given input. Euclid algorithm says the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. Here in this C program we first check which is the biggest number and assign it as numerator other as the denominator, then use the mod operator inside a while loop to find GCD or HCF.

What is LCM? How LCM is calculated in C?

LCM is the least common multiple of two numbers. It is the lowest positive integer that is divisible by both the numbers, suppose we have two numbers 4 and 6 which have their multiples and the least common multiple is 12. After finding the GCD or HCF, for LCM we have a well-defined formula.

"LCM = num1 * num2 / GCD".

Suppose when we take 2 numbers, say 'a' and 'b'. Let us take another number 'd' such that 'a/d' and 'b/d' don't leave any remainder or the remainder is zero, such types of numbers are called Common Divisors. Common divisor, 's' cannot be too big since divisors can't be larger than the number they are dividing. so 'd<=a' and "d<=b" conditions should be satisfied. 

ALGORITHM

STEP 1: Import the header libraries into the C program to use the built-in functions. 

STEP 2: Start the main program execution using void which means it doesn't return anything.

STEP 3: Initialize the variables for the Remainder, LCM, GCD, Numerator, Denominator, etc

STEP 4: Accept the two numbers from the user using printf and scanf Statements.

STEP 5: Use an if statement to check if num1 is greater than num2

STEP 6: if so assign the numerator as num1 and Denominator as num2

STEP 7: Use else to assign the vice versa if num2 is larger. 

STEP 8: Calculate the remainder by using the MOD operator between num1 and num 2.

STEP 9: Use the while loop until the remainder is not equal to Zero. 

STEP 10: Swap the numerator as denominator and denominator as remainder.

STEP 11: Assign the denominator as GCD.

STEP 12: Calculate the LCM  using Formula num1 * num2 / GCD;

STEP 13: Print the result of both GCD and LCM.

C Source Code

                                          #include <stdio.h>


void main() {
  int num1, num2, GCD, LCM, remainder, numerator, denominator; /* declares the variables gcd, lcm, remainder etc as integers  */
  printf("Enter two numbers\n");
  scanf("%d %d", & num1, & num2); /*  accepts two numbers from the user  */
  if (num1 > num2) {
    numerator = num1;
    denominator = num2;
  } else {
    /* checks and assigns the value for numerator and denominator  */
    numerator = num2;
    denominator = num1;
  }
  remainder = num1 % num2; /* use mod operator to find the remainder  */
  while (remainder != 0) {
    numerator = denominator; /* using Euclid's algorithm to interchange the values of variables  */
    denominator = remainder;
    remainder = numerator % denominator;
  }
  GCD = denominator;
  LCM = num1 * num2 / GCD;
  printf("GCD of %d and %d = %d \n", num1, num2, GCD); /* after gcd we find out the value of lcm */
  printf("LCM of %d and %d = %d \n", num1, num2, LCM);
} /* End of main() */
                                      

OUTPUT

RUN 1

Enter two numbers
5
15

GCD of 5 and 15 = 5
LCM of 5 and 15 = 15