Skip to main content

ProwessApps

Learn · Practice · Excel
About Contact
Login / Register

C Program to calculate hcf and lcm of two number

C Code Example — Loop Programs

ADVERTISEMENT

C Program to calculate hcf and lcm of two number

Objective

Write a C program to calculate the HCF (GCD) and LCM of two numbers.

Algorithm / Approach

  1. Read two numbers a and b.
  2. Determine which is the greater (gr) and which is the lower (low).
  3. Use a while(low != 0) loop to implement the Euclidean algorithm.
  4. Inside the loop: temp = gr % low, then gr = low, then low = temp.
  5. When the loop finishes, gr holds the HCF.
  6. Calculate the LCM using the formula: LCM = (a * b) / HCF.
main.c 
#include<stdio.h>
int main( ) {
 int a,b,temp,gr,low, lcm;
 printf("Enter two numbers : ");
 scanf("%d%d",&a,&b);
 gr = (a >= b)?a:b;
 low = (a < b)?a:b;
 while(low!=0) {
  temp = gr % low;
  gr = low;
  low = temp;
 }
 printf("HCF = %d\n",gr);
 lcm = a*b/gr;
 printf("LCM = %d\n",lcm); 
 return 0;
}

Expected Output

Enter two number : 30 40
HCF = 10
LCM = 120

Explanation of the Program

  • The Highest Common Factor (HCF) is the largest number that perfectly divides both numbers.
  • The Euclidean Algorithm is a highly efficient ancient mathematical method to find the HCF by repeatedly taking the remainder of the larger number divided by the smaller number until the remainder is 0.
  • The Least Common Multiple (LCM) is mathematically related to the HCF. The product of two numbers is always equal to the product of their HCF and LCM.

Complexity

Time Complexity O(log(min(a,b))) - Time complexity of the Euclidean algorithm.
Space Complexity O(1)
ADVERTISEMENT