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

July 6, 2021, Learn eTutorial
813

GCD or HCF is the Highest Common Divisor or Greatest Common Divisor of two numbers and LCM is the Least Common Multiple of two numbers. For a better understanding of this finding GCD or HCF and LCM C program example, we always recommend you to learn the basic topics of C programming listed below:

## What is GCD or HCF?

GCD or HCF of two numbers means the biggest number which can be able to divide both the numbers. Suppose we have two numbers 36 and 60 then the GCD or HCF is 12. Because

## How is GCD or HCF calculated in the C program?

To find GCD or LCM using the C program, we use Euclid's algorithm and the LCM of the given input.

Euclid's 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 the 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 the C program?

LCM is the Least Common Multiple of the two numbers. It is the lowest positive integer that is divisible by both numbers.

Suppose we have two numbers 4 and 6, to find the LCM  we have to find 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 divisors, '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```