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