### Greatest Common Divisor (Eucledian)

Greatest Common Divisor (GCD for short) is the largest positive integer that divides two numbers. In other words, the greatest common divisor of

The key thing in this algorithm is

Below is the theorem used for this algorithm:

Hope it helps anyone who needs it. Happy Programming :)

*a*and*b*is, as its name suggests, the largest positive integer*d*such that*d*|*a*and*d*|*b*. In this post, we will see how we can calculate GCD efficiently using an algorithm that is known as**Eucledian Algorithm**.The key thing in this algorithm is

*division with remainder*, which is simply the method of "long division" that you learned in elementary school. Thus if*a*and*b*are positive integers and if you attempt to divide*a*by*b*, you will get a quotient*q*and a reminder*r*.Below is the theorem used for this algorithm:

LetBelow is the sample source code on how it is implemented using the C programming languageaandbbe positive integers with a >= b. The following algorithm computes gcd(a,b) in a finite number of steps.

(1) Let r_{0}= a and r_{1}= b

(2) Set i = 1

(3) Divide r_{i-1}by r_{i}to get a quotient q_{i}and remainder r_{i+1}, r_{i-1}= r_{i}.q_{i}+ r_{i+1}with 0 <= r_{i+1}<= r_{i}

(4) If the remainder r_{i+1}= 0, then r_{i}=gcd(a,b) and the algorithm terminates.

(5) Otherwise, r_{i+1}> 0, so set i = i + 1 and go to Step 3.

int gcd ( int number1 , int number2 ) { if ( number2 == 0 ) return number1 ; else return gcd ( number2 , number1 % number2 ) ; }

Hope it helps anyone who needs it. Happy Programming :)

## Comments

## Post a Comment