C Program to Find Gcd of Two Numbers using Iterative Euclid’s Algorithm

General Introduction:

In one of our previous example, we calculated the gcd of two numbers recursively using Euclid’s algorithm. We can also find the gcd of two numbers using the iterative method for Euclid’s algorithm.

The concept is used in the calculation of gcd using iteration:
1) Take two numbers a and b as inputs.
2) If a==0, then gcd is b.
3) Else if b==0,then gcd is a.
4) Else,
while(b!=0){
r=a mod b;
a=b;
b=r;
}
And then gcd is a.

Code in C:

#include<stdio.h>
#include<conio.h>

int euclid_gcd(int,int);
int main()
{
	int a,b;
	int gcd;
	printf("Enter the first number: ");
	scanf("%d",&a);
	printf("\nEnter second number:");
	scanf("%d",&b);
	
	gcd=euclid_gcd(a,b);
	printf("The gcd of two numbers %d and %d is: %d",a,b,gcd);
	getch();
	return(0);
	
}

int euclid_gcd(int a,int b)
{
	int remainder;
	if(a==0)
	{
		return(b);
	}
	
	else if(b==0)
	{
		return(a);
	}
	
	else
	{
		while(b!=0)
		{
			remainder=a%b;
			a=b;
			b=remainder;
		}
		return(a);
	}
}

Outputs:

Please feel free to comment if you are confused in any of the steps.

Also Read: C Program to Execute Linear Search