Here is the C program to find LCM and HCF of two numbers. The least common multiple(LCM) of two integers a and b, usually denoted by LCM (a, b), is the smallest positive integer that is divisible by both a and b.
Algorithm to find LCM of two number
- Find the prime factorization of each of the two numbers.
48 = 2 × 2 × 2 × 2 × 3;
180 = 2 × 2 × 3 × 3 × 5;
- Create set of prime factor for both numbers.
Set-48 = {2, 2, 2, 2, 3}
Set-180 = {2, 2, 3, 3, 5}
- Find common elements in both set.
Set-Common = {2, 2, 3}
- Now Combine elements of Set-48 and Set-180 in one set.
Set-Combined = Set-48 and Set-180
Set-Combined = {2, 2, 2, 2, 3} + {2, 2, 3, 3, 5}
Set-Combined = {2, 2, 2, 2, 2, 2, 3, 3, 3, 5}
- Now, Set-LCM = Set-Combined - Set-Common
Set-LCM = {2, 2, 2, 2, 2, 2, 3, 3, 3, 5} - {2, 2, 3}
Set-LCM = {2, 2, 2, 2, 3, 3, 5}
- LCM (48, 180) = Product of all elements of Set-LCM
LCM (48, 180) = 2 × 2 × 2 × 2 × 3 × 3 × 5
LCM (48, 180) = 720
The highest common factor(HCF) of two or more integers, is the largest positive integer that divides the numbers without a remainder. HCF is also known as greatest common divisor(GCD) or greatest common factor(GCF).
Algorithm to find HCF or GCD of two number
- Find the prime factorization of each of the two numbers.
48 = 2 × 2 × 2 × 2 × 3;
180 = 2 × 2 × 3 × 3 × 5;
- Create set of prime factor for both numbers.
Set-48 = {2, 2, 2, 2, 3}
Set-180 = {2, 2, 3, 3, 5}
- Find common elements in both set.
Set-Common = {2, 2, 3}
- GCD (48, 180) = Product of all elements of Set-Common
GCD (48, 180) = 2 × 2 × 3
GCD (48, 180) = 12
If we know LCM or HCF of two numbers, then we can find the other one using below equation.
LCM(A, B) X HCF(A, B) = A*B
C program to find LCM and HCF of two numbers using loop
#include <stdio.h>
int main() {
int a, b, num1, num2, temp, gcd, lcm;
printf("Enter two numbers\n");
scanf("%d %d", &a, &b);
num1 = a;
num2 = b;
while (num2 != 0) {
temp = num2;
num2 = num1 % num2;
num1 = temp;
}
gcd = num1;
lcm = (a*b) / gcd;
printf("GCD of %d and %d is %d\n", a, b, gcd);
printf("LCM of %d and %d is %d\n", a, b, lcm);
return 0;
}
Output
Enter two numbers 48 180 GCD of 48 and 180 is 12 LCM of 48 and 180 is 720
C program to find LCM and HCF of two numbers using recursion
#include <stdio.h>
int getGcd(int a, int b);
int main(){
int num1, num2, gcd, lcm;
printf("Enter two numbers\n");
scanf("%d %d", &num1, &num2);
gcd = getGcd(num1, num2);
lcm = (num1 * num2)/ gcd;
printf("GCD of %d and %d is %d\n",
num1, num2, gcd);
printf("LCM of %d and %d is %d\n",
num1, num2, lcm);
return 0;
}
int getGcd(int a, int b) {
if (b == 0) {
return a;
}
else {
return getGcd(b, a % b);
}
}
Output
Enter two numbers 4 38 GCD of 48 and 180 is 2 LCM of 48 and 180 is 76
Related Topics