You are here

C program to find HCF and LCM

C program to find HCF and LCM: The code below find the highest common factor and the least common multiple of two integers. HCF is also known as the greatest common divisor (GCD) or the greatest common factor (GCF).

C programming code

  1. #include <stdio.h>
  2.  
  3. int main() {
  4.   int a, b, x, y, t, gcd, lcm;
  5.  
  6.   printf("Enter two integers\n");
  7.   scanf("%d%d", &x, &y);
  8.  
  9.   a = x;
  10.   b = y;
  11.  
  12.   while (b != 0) {
  13.     t = b;
  14.     b = a % b;
  15.     a = t;
  16.   }
  17.  
  18.   gcd = a;
  19.   lcm = (x*y)/gcd;
  20.  
  21.   printf("Greatest common divisor of %d and %d = %d\n", x, y, gcd);
  22.   printf("Least common multiple of %d and %d = %d\n", x, y, lcm);
  23.  
  24.   return 0;
  25. }

Download HCF and LCM program.

Output of program:
HCF and LCM c program

C program to find hcf and lcm using recursion

  1. #include <stdio.h>
  2.  
  3. long gcd(long, long);
  4.  
  5. int main() {
  6.   long x, y, hcf, lcm;
  7.  
  8.   printf("Enter two integers\n");
  9.   scanf("%ld%ld", &x, &y);
  10.  
  11.   hcf = gcd(x, y);
  12.   lcm = (x*y)/hcf;
  13.  
  14.   printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf);
  15.   printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm);
  16.  
  17.   return 0;
  18. }
  19.  
  20. long gcd(long a, long b) {
  21.   if (b == 0) {
  22.     return a;
  23.   }
  24.   else {
  25.     return gcd(b, a % b);
  26.   }
  27. }

C program to find hcf and lcm using function

  1. #include <stdio.h>
  2.  
  3. long gcd(long, long);
  4.  
  5. int main() {
  6.   long x, y, hcf, lcm;
  7.  
  8.   printf("Enter two integers\n");
  9.   scanf("%ld%ld", &x, &y);
  10.  
  11.   hcf = gcd(x, y);
  12.   lcm = (x*y)/hcf;
  13.  
  14.   printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf);
  15.   printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm);
  16.  
  17.   return 0;
  18. }
  19.  
  20. long gcd(long x, long y) {
  21.   if (x == 0) {
  22.     return y;
  23.   }
  24.  
  25.   while (y != 0) {
  26.     if (x > y) {
  27.       x = x - y;
  28.     }
  29.     else {
  30.       y = y - x;
  31.     }
  32.   }
  33.  
  34.   return x;
  35. }