Find HCF and LCM in C Programming

C program to find HCF (Highest Common Factor) and LCM( Least Common Multiple): Today I will write a program on how to find HCF and LCM of two integers. HCF is also known as Greatest Common Divisor(GCD) or Greatest Common Factor(GCF).

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

1. Find HCF and LCM using Loop
2. Find HCF and LCM using Recursion
3. 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.