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:

C Program to Find Gcd of Two Numbers using Iterative Euclid's Algorithm 1
When the second number is 0.
C Program to Find Gcd of Two Numbers using Iterative Euclid's Algorithm 2
When the first number is 0.
C Program to Find Gcd of Two Numbers using Iterative Euclid's Algorithm 3
When none of the two numbers are 0.

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

Also Read: C Program to Execute Linear Search

LEAVE A REPLY

Please enter your comment!
Please enter your name here