How To Find GCD And LCM In C.
Today in c programming tutorial for beginners tutorial will be about how to find GCD and LCM between 2 numbers. Before starting the problem I want to share with you something about these problems. You will not find usage of these codes now. But when you will start contest programming and problem-solving in an online judge platform. You will find how useful and how important these codes were. Especially finding GCD is a common and most needed part of programming. This one is one of the favorite topics for the problem setter. However, without wasting any more time let’s get started.
So, in this tutorial you are going to learn the following things:
- How You Can Find The GCD Of Two Numbers In C.
- How You Can Find The LCM Of Two Numbers In C.
How To Find The GCD Of Two Numbers Using C Program:
I think you know what is the GCD of two numbers means. But I will try to explain it briefly. GCD means Greatest Common Divisor. When we need to find GCD between two numbers. We actually have to find the largest divisor of them. Means suppose we have to find GCD between 12 and 30. Then divisors of 12 are 1, 2, 3, 4, 6, 12 and divisors of 30 are 1, 2, 3, 5, 6, 10, 15, 30. Among them, common divisors of 12 and 30 are 1, 2, 3, and 6. So, we can call these numbers are common divisors of 12 and 30. And among these common divisors, 6 is the largest one. So, we can say that 6 is the greatest common divisor of 12 and 30.
Now, our task is to write a code in c that will find the greatest common divisor of 2 numbers. At first, see my code then I will explain it.
Code:
#include<stdio.h>
int main()
{
int a,b;
scanf(“%d%d”,&a,&b);
if(a==0)
{
printf(“GCD is %dn”,b);
}
else
{
while(b!=0)
{
if(a>b)
{
a=a-b;
}
else
{
b=b-a;
}
}
printf(“GCD is %dn”,a);
}
return 0;
}
Input: 5 25
Output: GCD is 5
Input: 12 30
Output: GCD is 6
Here, when a is 0 we have no doubt that gcd is b. Similarly when b is 0 then a is the GCD. But in the case of a and b, both are not 0. Then we will store the gcd in a. When a is greater than b then no doubt a is not the gcd. Also, gcd can’t be greater than b. So, we will subtract b from a. similarly when b is greater than a. This time also gcd can’t be either b or greater than a. So, we will subtract a from b. This process will continue until a is equal to b. For that time after the operation b=b-a. b will become 0 and we will find the gcd on a as a is not changing at the last operation. In this way, we can easily find gcd between any 2 numbers.
If x is the highest number between a and b then the complexity of this program is O(x).
How To Find LCM Of Two Numbers Using C Programming:
LCM means Least Common Multiple. You can say this was the opposite of GCD. Here we have to find the smallest number which is the smallest multiplication of the given 2 numbers. This means this is the smallest number that is divisible by both given number. For example, suppose we have to find the LCM of 6 and 10. So, the smallest number which is divisible by both 6 and 10 is 30. So, LCM of 6 and 10 is 30. Now, we have to write the code to determine the lcm of two given numbers.
Code:
#include<stdio.h>
int main()
{
int a,b;
scanf(“%d%d”,&a,&b);
int lcm;
if(a>b)
{
lcm=a;
}
else
{
lcm=b;
}
while(1)
{
if(lcm%a==0&&lcm%b==0)
{
break;
}
lcm++;
}
printf(“LCM is %dn”,lcm);
return 0;
}
Input: 6 10
Output: LCM is 30
Input: 12 18
Output: LCM is 36
Here, at first, we determined the largest number between a and b and store this on the lcm variable. As lcm of them can’t be less than the highest number between them. Then we just check if the lcm is divisible by both a and b. If yes then we terminate the loop by break operation. Otherwise, we increase the lcm by 1 and check this again. This process is continue until we find the 1st number which is divisible by both a and b. When we find the lcm then we terminate the loop and print the answer.
As lcm of a and b can’t be greater than a*b. So, the complexity of this program is O(a*b).
Now your question is in the above 2 programs I have used while() {…} and what the hell is this?😡 . Okay 😜. Be cool. This is called loop statement in c. Which is a more advanced level than we are currently. So, in the next tutorial, we are going to learn about loop statements in c. Till the next tutorial stay well. Be safe. Be smart. Of course, wear a mask and wash your hands. Happy coding😊.
