Introduction
GCD stands for Greatest Common Divisor, also known as HCF, which stands for Highest Common Factor. GCD/HCF of two numbers is the largest number that divides both of them completely, i.e., leaving no remainder.
Also Read, Binary to Hex Converter,C Static Function
Approach
Simple/Basic Approach
As GCD is the largest number that divides both the numbers completely, we can find the prime factors of both the numbers and the product of the intersection of all the factors present in both the numbers will be the GCD. Or we can find the largest number, which divides both numbers completely.
For Example, in order to calculate GCD of 12 and 16 :
factors of 12 = 1, 2, 3, 4, 6, 12
factors of 16= 1, 2, 4, 16
The largest number, which is a factor of both 12 and 16, is 4. Hence the GCD of 12 and 16 is 4.
Example
#include <stdio.h>
int main()
{
int num1, num2, GCD;
printf("Enter two integers whose GCD is to be calculated : ");
scanf("%d %d", &num1, &num2);
for(int i=1; i <= num1 && i <= num2; ++i)
{
// Checks if i is factor of both integers
if(num1%i==0 && num2%i==0)
GCD = i;
}
printf("G.C.D of %d and %d is %d", num1, num2, GCD);
return 0;
}
Output
Enter two integers whose GCD is to be calculated : 12 16
G.C.D of 12 and 16 is 4
Time Complexity : In the above code, we have only one loop with two termination conditions which are i<num1 and i<num2. As a result of which the loop will run till i<max(num1,num2). And therefore the time complexity will be O(max(num1,num2))
Space Complexity : No extra space is used. Therefore, the space complexity will be O(1)
Efficient Approach
GCD can also be calculated using the Euclidean algorithm. The main idea behind this algorithm is that the GCD of the two numbers doesn’t change if a smaller number is subtracted from the bigger number.
Iterative Approach
#include <stdio.h>
int main()
{
int num1, num2;
printf("Enter two integers whose GCD is to be calculated : ");
scanf("%d %d",&num1,&num2);
// if any number is negative, make it positive
num1 = ( num1 > 0) ? num1 : -num1;
num2 = ( num2 > 0) ? num2 : -num2;
while(num1!=num2)
{
if(num1 > num2)
num1 -= num2;
else
num2 -= num1;
}
printf("GCD = %d",num1);
return 0;
}
Output
Enter two integers whose GCD is to be calculated : 12 16
GCD = 4
You can practice by yourself with the help of online c compiler.
Recursive Approach
#include <stdio.h>
int gcd(int num1, int num2)
{
if (num1 == 0)
return num2;
if (num2 == 0)
return num1;
if (num1 == num2)
return num1;
//subtract the smaller number from the bigger number
if (num1 > num2)
return gcd(num1-num2, num2);
return gcd(num1, num2-num1);
}
int main()
{
int num1,num2;
printf("Enter two integers whose GCD is to be calculated : ");
scanf("%d %d",&num1,&num2);
printf("GCD of %d and %d is %d ", num1, num2, gcd(num1, num2));
return 0;
}
Output
Enter two integers whose GCD is to be calculated : 12 16
GCD of 12 and 16 is 4
Time complexity: The program will run until num1 becomes equal to num2. In each iteration, we subtract the smaller number from the larger number. Therefore the time complexity will be O(max(num1,num2)) for both the iterative and recursive approach.
Space Complexity: No extra space is used. Therefore, the space complexity will be O(1) for the iterative approach whereas it would be O(max(num1,num2)) for the recursive approach which would be taken by the recursive call-stack.
You can also read about dynamic array in c, and Tribonacci Series
A more efficient is to use a modulo operator.
Example
#include <stdio.h>
int GCD(int num1, int num2)
{
if (num2 == 0)
return num1;
return GCD(num2, num1 % num2);
}
int main()
{
int num1,num2;
printf("Enter two integers whose GCD is to be calculated : ");
scanf("%d %d",&num1,&num2);
int gcd=GCD(num1,num2);
printf("GCD of %d and %d : %d ", num1, num2, gcd);
}
Output
Enter two integers whose GCD is to be calculated : 12 16
GCD of 12 and 16 : 4
Time Complexity
The time complexity for the above program will be O(log(max(num1,num2))) which is obtained from the analysis of the worst-case scenario. Inorder to complete the program in 1 step, the numbers required would be (1,1). Inorder to complete the program in 2 steps, the numbers required would be (1,2). Similarly for 3 steps we would require (2,3), for steps we would require (3,5) and so on. It can be observed that for the nth step the numbers we would require would be (fib(n),fib(n+1)). The worst-case time complexity would be O(n) where num1>=fib(n) and num2>=fib(n+1)
The Fibonacci series is an exponentially growing series where the ratio of nth/(n-1)th term approaches (sqrt(5)-1)/2. It can be observed that the time complexity of the algorithm increases linearly as the terms grow exponentially. Therefore the time complexity would be O(log(max(num1,num2))).
Space Complexity
The space complexity of the above program will be O(log(max(num1,num2))) which would be taken up by the recursive call stack.
Read More - Time Complexity of Sorting Algorithms and Short int in C Programming
40+ registered 
