C Program to Find GCD

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));
}

 

 

Sonam Dargay

Kuzu Zangpo la! I am Sonam Dargay, a student in the College of Science and Technology affiliated to The Royal University of Bhutan. I am a tech enthusiast student, studying Bachelor of Engineering in Information Technology.

You may also like...

%d bloggers like this: