GCD and LCM Program in C

Flow Control
If-else Statement in C
Programs on if-else
Switch Case in C
Switch case Programs
Conditional Operator
While loop in C
Do-while loop in C
While vs do-while
For loop in C
Break keyword in C
Continue keyword in C
Break vs Exit in C
Goto keyword in C
☕️ Flow Control Programs
Largest in 3 Numbers
Find Grade of student
Find the absolute value
Vowel or Consonant
Leap Year Program
Simple calculator in C
Check Odd or Even 
Roots of Quadratic Equation
Find Reverse of Number
Factors of a number in C
Generate Multiplication table
Find Power of a Number
Find GCD and LCM
Find factorial of Number
Count Number of Digits
Sum of digits in Number
Sum of N Natural Numbers
Sum of Squares of Natural No.
Find Sum of Odd Numbers
Find the Sum of Series
Find Fibonacci series in C
Sum of the Fibonacci series
Sum until enters +ve numbers
Sum of max 10 no. & Skip -ve
☕️ C Conversion Programs
Celsius to Fahrenheit
Fahrenheit to Celsius
Decimal ↔ Binary
Decimal ↔ Octal
Octal ↔ Binary in C
☕️ Number Programs in C
Prime Number in C
Strong Number in C
Krishnamurthy Number
Neon Number in C
Palindrome number
Perfect Number in C
Armstrong Number
☕️ Pattern Programs in C
Pattern programs in C
Printing pattern using loops
Floyd’s triangle Program
Pascal Triangle Program
Pyramid Star Pattern in C
Diamond Pattern Programs
Half Diamond pattern in C
Print Diamond Pattern
Hollow Diamond Pattern
Diamond Pattern of Numbers

LCM and HCF program in C | GCD and LCM program in C | HCF and LCM program in C

The highest common factor (HCF) of two or more numbers is the greatest number that divides each of them exactly. Greatest Common Measure(GCM) and Greatest Common Divisor(GCD) are the other terms used to refer to HCF. Example: HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.

C Program to Find GCD or HCF of two Numbers

 #include<stdio.h>
 int main()
 {
     int num1, num2, i, gcd;

     printf("Enter two numbers: ");
     scanf("%d %d", &num1, &num2);

     for(i=1; i<=num1 && i<=num2; i++)
     {
         if(num1%i==0 && num2%i==0)
             gcd=i;
     }

     printf("GCD = %d\n",gcd);

     return 0;
 }

Output:-

Enter two numbers: 12 16
GCD = 4

GCD or HCF using while loop

In the previous program, we use for loop to find gcd of the two numbers. We can also use a while loop to do the same.

 #include<stdio.h>
 int main()
 {
     int num1, num2;

     printf("Enter two positive integers: ");
     scanf("%d %d", &num1, &num2);

     while(num1 != num2)
     {
         if( num1 > num2 )
             num1 -= num2; // num1= num1 - num2
         else
             num2 -= num1; //num2= num2 - num1
     }

     printf("GCD = %d\n",num1);

     return 0;
 }

Output:-

Enter two positive integers: 15 18
GCD = 3

C Program to Find LCM of two Numbers

Least or lowest common multiple (LCM) of two integers a and b is the smallest positive number that is divisible by both a and b.

#include<stdio.h>
int main()
{
     int num1, num2, minmultiple;

     printf("Enter two numbers: ");
     scanf("%d %d", &num1, &num2);

     // minmultiple will be equal to smaller number
     minmultiple= (num1<num2) ? num1:num2 ;

     while(1) // always true
     {
         if( minmultiple % num1 == 0 && minmultiple % num2 == 0 )
         {
             printf("LCM = %d\n", minmultiple);
             break;
         }
         minmultiple++;
     }

     return 0;
}

Output:-

Enter two numbers: 12 16
LCM = 48

C Program to Find LCM Using GCD

The product of two numbers a and b is equal to the product of GCD(a,b) and LCM(a,b).

a*b = GCD(a,b) * LCM(a,b)

Using this formula we can find GCD and LCM at a time. We need to find either GCD and LCM and then apply this formula.

In the below program, we find GCD then the above formula is used to find the LCM. The Formula used for this purpose is:-
LCM (a,b) = (a*b) / GCD (a,b)

The below program finds LCM and GCD of two numbers.

 #include<stdio.h>
 int main()
 {
     int num1, num2, i, gcd, lcm;

     printf("Enter two numbers: ");
     scanf("%d %d", &num1, &num2);

     for(i=1; i<=num1 && i<=num2; i++)
     {
         if(num1%i==0 && num2%i==0)
             gcd=i;
     }

     lcm=(num1*num2)/gcd;

     printf("GCD = %d\n",gcd);
     printf("LCM = %d\n",lcm);

     return 0;
 }

Output:-

Enter two numbers: 15 18
GCD = 3
LCM = 90

We can find HCF using LCM also. The Formula used for this purpose is:- HCF (a,b) = (a*b) / LCM (a,b)

We can solve the same problem using recursion techniques also:- C Program to Find GCD of Two Numbers Using Recursion

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Flow Control
If-else Statement in C
Programs on if-else
Switch Case in C
Switch case Programs
Conditional Operator
While loop in C
Do-while loop in C
While vs do-while
For loop in C
Break keyword in C
Continue keyword in C
Break vs Exit in C
Goto keyword in C
☕️ Flow Control Programs
Largest among 3 Numbers
Find Grade of student
Find the absolute value
Check Vowel or Consonant
Leap Year Program
Simple calculator in C
Check Odd or Even 
Roots of Quadratic Equation
Find Reverse of Number
Factors of a number in C
Generate Multiplication table
Find Power of a Number
Find GCD and LCM
Find factorial of Number
Count Number of Digits
Sum of digits in Number
Sum of N Natural Numbers
Sum of Squares of Natural No.
Find Sum of Odd Numbers
Find the Sum of Series
Find Fibonacci series in C
Sum of the Fibonacci series
Sum until enters +ve numbers
Sum of max 10 no. & Skip -ve
☕️ C Conversion Programs
Celsius to Fahrenheit
Fahrenheit to Celsius
Decimal ↔ Binary
Decimal ↔ Octal
Octal ↔ Binary in C
☕️ Number Programs in C
Prime Number in C
Strong Number in C
Krishnamurthy Number
Neon Number in C
Palindrome number
Perfect Number in C
Armstrong Number
☕️ Pattern Programs in C
Pattern programs in C
Printing pattern using loops
Floyd’s triangle Program
Pascal Triangle Program
Pyramid Star Pattern in C
Diamond Pattern Programs
Half Diamond pattern in C
Print Diamond Pattern
Hollow Diamond Pattern
Diamond Pattern of Numbers

Leave a Comment

Your email address will not be published. Required fields are marked *