C program to find HCF (**H**ighest **C**ommon **F**actor) and LCM( **L**east **C**ommon **M**ultiple): Today I will write a program on how to find HCF and LCM of two integers. HCF is also known as **G**reatest **C**ommon **D**ivisor(GCD) or **G**reatest **C**ommon **F**actor(GCF).

Here there are three methods to find HCF and LCM in C Programming as follow:

- Find HCF and LCM using Loop
- Find HCF and LCM using Recursion
- Find HCF and LCM using Function

## Find HCF and LCM in C Programming using Loop

/** Write a c program to find hcf and lcm using Loop **/ #include <stdio.h> int main() { int a, b, x, y, t, gcd, lcm; printf("Enter two integers\n"); scanf("%d%d", &x, &y); a = x; b = y; while (b != 0) { t = b; b = a % b; a = t; } gcd = a; lcm = (x*y)/gcd; printf("Greatest common divisor of %d and %d = %d\n", x, y, gcd); printf("Least common multiple of %d and %d = %d\n", x, y, lcm); return 0; }

Output of C Program:

Enter two integers 9 24 Greatest common divisor of 9 and 24 = 3 Least common multiple of 9 and 24 = 72

## Find HCF and LCM in C Programming using Recursion

/** Write a c program to find hcf and lcm using Recursion **/ #include <stdio.h> long gcd(long, long); int main() { long x, y, hcf, lcm; printf("Enter two integers\n"); scanf("%ld%ld", &x, &y); hcf = gcd(x, y); lcm = (x*y)/hcf; printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf); printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm); return 0; } long gcd(long a, long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } }

## Find HCF and LCM in C Programming using Function

/** Write a c program to find hcf and lcm using Function **/ #include <stdio.h> long gcd(long, long); int main() { long x, y, hcf, lcm; printf("Enter two integers\n"); scanf("%ld%ld", &x, &y); hcf = gcd(x, y); lcm = (x*y)/hcf; printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf); printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm); return 0; } long gcd(long x, long y) { if (x == 0) { return y; } while (y != 0) { if (x > y) { x = x - y; } else { y = y - x; } } return x; }

Please comment if this code is useful to you or having any queries.