# GCD and LCM Program in C

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!