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:

**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

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**.

**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.

**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**.

` ````
#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() */
```

RUN 1 Enter two numbers 5 15 GCD of 5 and 15 = 5 LCM of 5 and 15 = 15