gcd of two numbers in C

gcd of two numbers
gcd of two numbers in C

gcd of two numbers in C

Problem Statement: Given two numbers, Find the gcd of two given numbers.

Examples:

Example 1: 
Input: n1 = 4, n2 = 8
Output: 4

Example 2:
Input: n1 = 2, n2 = 4
Output: 2

DisclaimerDon’t jump directly to the solution, try it out yourself first.

What is GCD?

GCD is defined as the greatest common divisor of two numbers. Have you heard of H.C.F. in elementary mathematics? GCD is exactly same as HCF.

For example, G.C.D of 4 and 8 will be 4 as 4 is the largest number which divides both 4 and 8.

Similarly, G.C.D. of 12 and 18 will be 6 as 6 is the largest number which divides both 12 and 18.

Approach:

As we learned above that the GCD of two integers is the largest integer that divides both the integers.

Therefore, we will run a loop from i = 1 to min(n1, n2) and find the largest integer that divides both n1 and n2.

Code:

C Program

#include <stdio.h>
#include <math.h>
int min(int a, int b)
{
    if(a<b)
    return a;
    return b;
}
int gcd(int n1,int n2)
{
    int gcdd = 1;
    for(int i=1;i<=min(n1,n2);i++)
    {
        if(n1%i==0&&n2%i==0)
        gcdd=i;
    }
    return gcdd;
}

int main() {
	int n1 = 5, n2 = 10;
	printf("The GCD of the two integers %d and %d is %d",n1,n2,gcd(n1,n2));
	return 0;
}

Output: The GCD of the two integers 5 and 10 is 5

Time Complexity: O(min(n1,n2))

Space Complexity: O(1)

Can the above program be further optimized?

A simple optimisation in the above program can be to run the loop in reverse order starting from min(n1,n2) to 1 and breakout from the loop as soon as you find a divisor.

This will change the best case time complexity to O(1)

Special thanks to Subhrajit Das for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article