The gcd of two numbers is the largest number which divides the tow numbers with out leaving any reminder. gcd often known as greatest common factor (GCF), the highest common factor (HCF), and the greatest common measure (GCM).
In this post I will explain the calculation of GCD of tow numbers with Euclidean algorithm. This algorithm is recursive. So we can use recursion in any programming language which supports recursion to calculate GCD with Euclidean algorithm.
According to the algorithm the GCD of the two numbers will not change if the larger number is replaced with the difference of the small number and large number.
In each step of recursion we have to replace the large number with the difference of the small number and large number.
The implementation of the Euclidean algorithm for the problem is as simple as below
int calculateGCD (int num1 , int num2)
{
if ( num2 == 0 )
{
return num1;
}
else if ( num1== 0 )
{
return num2;
}
return calculateGCD ( num2 , num1 % num2 );
}
in this algorithm we are returning the number if that is zero as a pre check. If both the numbers passed to the algorithm are non zeros then we have call the function itself till any one of the number becomes. in lase step when one of the number becomes zero we will return the number which is not zero to the previous step.
In this post I will explain the calculation of GCD of tow numbers with Euclidean algorithm. This algorithm is recursive. So we can use recursion in any programming language which supports recursion to calculate GCD with Euclidean algorithm.
According to the algorithm the GCD of the two numbers will not change if the larger number is replaced with the difference of the small number and large number.
In each step of recursion we have to replace the large number with the difference of the small number and large number.
The implementation of the Euclidean algorithm for the problem is as simple as below
int calculateGCD (int num1 , int num2)
{
if ( num2 == 0 )
{
return num1;
}
else if ( num1== 0 )
{
return num2;
}
return calculateGCD ( num2 , num1 % num2 );
}
in this algorithm we are returning the number if that is zero as a pre check. If both the numbers passed to the algorithm are non zeros then we have call the function itself till any one of the number becomes. in lase step when one of the number becomes zero we will return the number which is not zero to the previous step.
