What do you mean by GCD?
GCD stands for Greatest Common Divisor which is a common factor number which exactly divides two or more numbers.
Let us see a scenario which gives a better understanding on what GCD is?
Say we are given two natural numbers and we have to find a number which exactly divides those two numbers what are we going to do?
How to Compute GCD?
We try to compute the GCD of those two numbers so that the greatest common factor is obtained so it turns out to be dividing them.
Now let us try to compute the GCD of two numbers:
Say we have 24 and 36 and we are given a task to obtain the GCD of those two numbers it is mathematically done this way:
Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
Now let us try to check which is the number repeating in both the cases and confirm the largest among them here in this case we are having 12 in both 24 and 36 factors so 12 is the GCD.
Now let us compute it in C:
#include<stdio.h>
int gcd(int n, int m){ //declaration of gcd function
if(n==0){ // check whether the value of n is zero if zero then m is printed
return m;
}
else{
return(gcd(m%n,n)); //else then your gcd will be computed the dry run is given below
}
}
int main(){
int n,m;
scanf("%d %d",&n,&m); //inputting the integers
printf("The gcd of n is: "); //printing the value
int s = gcd(n,m); //a recursion call which will help us computing the gcd.
printf("%d", s);
}
//
Recursion Call:
A recursive function is a function that calls itself, either directly or indirectly. The function must have a base case, which is a case where the function does not call itself, and a recursive case, which is a case where the function calls itself.
///
/*Dry Run:
the number are 36 and 24
Now return(gcd(m%n,n)); condition is to be checked:
gcd(36%24,36) // % is modulusdivision operator which will return us the remainder
now the remainder is 36%24-- 12
so the new updated scenario is:
gcd(24%12,12)
now the remainder is 24%12-- 12
gcd(12%12, 12)
now the remainder is 12%12 -- 0
so what ever is on our right side which is the m value is our gcd so in this scenario it is 12.
*/