March 11, 2012| | 0 Comment
The Euclidean Algorithm (GCD Algorithm)
The blog is intended to demonstrate the Euclidean Algorithm, used to find Greatest Common Divisor (GCD) value of Two Numbers (the oldest Algorithm known, it appeared in Euclid’s Elements around 300 BC).
Step 1: About Euclidean Algorithm
Our aim is to find GCD (a, b) of two numbers a and b.
Suppose a is smaller than b…..
1. To find GCD, divide the b by a, if we get reminder zero then …..We done it….B’coz b is multiple of a.
2. If NOT then again divide the Divisor by Reminder until we get reminder equal to zero.
3. The Last Non-Zero reminder is the GCD value of a and b.
In Step 1, we mention only one possibility of Euclidean Algorithm, but there are two more possibilities to find GCD Value between two numbers.
Possibility #2: a == b [a exactly equal to b]
Possibility #3: a > b [a greater than b]
Here I implemented the Code for all these Three possibilities
1. Accept two numbers from User. Declare the variable reminder = 1.
2. The Code for Possibility #1 (a < b)
3. The Code for Possibility #2 (a == b) & Possibility #3 (a > b)
4. Now execute the Application and see the result (Figure 1).
In this piece of writing, we have seen the implementation of The Euclidean Algorithm. For writing the code here I used the C# Language.