C Program to Find GCD: This post discusses how to write C program to find GCD. There are many approaches to find the greatest common divisor (GCD) of any two numbers. It is the highest number that can divide both the numbers.
The commonly used method to find the GCD of any two numbers is known as the Euclidian Algorithm which is a recursive approach which can be mathematically shown as:
GCD(a, b)={b, if b divides a
{GCD(b, a%b) otherwise
Sample Code
#include<stdio.h>
//using Euclid's algorithm
/*
GCD(a, b)={b, if b divides a
{GCD(b, a%b) otherwise
*/
int GCD(int, int);
main()
{
int num1, num2, res;
printf("Enter the two numbers:");
scanf("%d %d",&num1, &num2);
res=GCD(num1, num2);
printf("\nGCD of %d and %d is %d", num1, num2, res);
return 0;
}
int GCD(int x, int y)
{
int rem;
rem=x%y;
if(rem==0)
return y;
else
return(GCD(y, rem));
}