Greatest Common Divisor

Hi all, In this post I will be telling you about GCD. GCD as you all know stands for Greatest Common Divisor. GCD of two or more integers, when at least one of them is not zero, is the largest positive integer that divides without a remainder. For example GCD of 15 and 25 is 5. The Gcd can be implemented either in iterative or recursive manner.

int gcdi(int a,int b){        //iterative

	while(a!=b){
		if(a>b)
			a = a-b;
		else
			b=b-a;
	}
	return a;
}

int gcdr(int a , int b){			//recursive

if(b>a)return gcdr(b,a);
if(b==0)return a;
else
	return gcdr(b,a%b);
}

The STL algorithm library implements an inbuilt function named __gcd(a,b). gcd(a,b), where a and b are not both zero, may be defined as the smallest positive integer d for which can be written in the form d=a.p+b.q where p and q are integers.