The highest common factor (HCF) of two whole numbers is defined as the largest whole number which is factor to both the numbers. On the other hand, Least Common Multiple (LCM) is the smallest common multiple of the whole numbers. Both HCF and LCM carry a great significance in mathematics, physics and engineering.
Writing a program to find the HCF and LCM of two whole numbers is a popular tutorial/question in C programing language. It gives the idea of basic loop techniques, some mathematical operations along with the fundamental input output functions of C library.
The basic working principle of finding HCF and LCM is division of the numbers in a loop. Initially, a number is divided by another number and the remainder is assigned to a variable. Then, the number is again divided by the remainder. The process is continued till the remainder is found to be zero and thus, HCF is finalized.
Algorithm to find HCF and LCM:
- Start
- Declare variables
- Enter the whole numbers whose LCM and HCF are to be determined
- Equalize the variable with temporary variables
- Divide one number by another and store the remainder in loop
- Keep on dividing the number by successive remainder till the remainder becomes zero in loop
- Assign the remainder with HCF
- LCM = product of numbers / HCF
- Print the finalized LCM and HCF
- Stop
Source Code in C to Find HCF and LCM:
As C is a flexible programming language, there are various ways of solving a same problem. Here, are two different source codes for finding HCF and LCM: the first one is without using function and the second one uses user defined function.
Without Using Function:
#include <stdio.h>
int main()
{
int m, n, a, b, t, hc, lc; // variable declaration
printf(" Enter two numbers: ");
scanf("%d%d", &a, &b);
m = a;
n = b;
while (n != 0)
{
t = n;
n = m % n;
m = t;
}
hc = m; // hcf
lc = (a*b)/hc; // lcm
printf(" The highest Common Factor %d and %d = %d\n", a, b, hc);
printf(" The Least Common Multiple of %d and %d = %d\n", a, b, lc);
return 0;
}
When this program is executed, it simply asks for the numbers of which HCF and LCM are to be determined. Then, all the division mechanism as mentioned in algorithm is performed in the while loop and HCF is finalized. With help of HCF, the LCM of whole number is calculated.
Using Function:
#include <stdio.h>
long fun(long, long); // function declaration
int main()
{
long a, b, hc, lc;
printf("Enter two numbers: ");
scanf("%ld%ld", &a, &b);
hc = fun(a, b);// Function Calling
lc = (a*b)/hc;
printf(" The highest Common Factor of %ld and %ld = %ld\n", a, b, hc);
printf(" The Least Common Multiple of %ld and %ld = %ld\n", a, b, lc);
return 0;
}
long fun(long a, long b) // Function definition
{
if (a == 0)
{
return b;
}
while (b != 0) {
if (a > b) {
a = a - b;
}
else {
b = b - a;
}
}
return a;
}
In this program, the whole division process is performed in the user defined function named as fun() with two long integers as arguments. The function fun() is called to find the value of HCF and the return value of the called function is used to calculate the LCM. A common output of both the programs is presented below:
I hope this tutorial on finding HCF and LCM of a whole number using C language was helpful to understand the basic looping techniques and mathematical operations in C language. Both the source codes are simple and easy to understand; they should be compiled on Code::Blocks IDE.
If you have any queries or suggestion regarding any content of the post – the source code or algorithm, mention them below in the comments. You can find more C tutorials here.
