Description:
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).
GCD Value: -
Is
the Largest number dividing the both numbers
Justification:
Step 1: About Euclidean
Algorithm
Possibility #1:
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.
Step 2:
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
The Code:
1.
Accept
two numbers from User. Declare the variable reminder = 1.
Console.Write("\n\t\tValue-1
: ");
long x = Int32.Parse(Console.ReadLine());
Console.Write("\n\t\tValue-2
: ");
long y = Int32.Parse(Console.ReadLine());
long
reminder = 1;
Listing
1
2.
The
Code for Possibility
#1 (a < b)
if (x > y)
{
if (x % y == 0) { reminder = y; }
else
{
reminder = x % y;
if (reminder != 0) { reminder = reminder % y; }
}
}
Listing 2
3. The Code for Possibility
#2 (a == b) & Possibility #3 (a > b)
else if (x == y || x
< y)
{
if (y % x == 0) { reminder = x; }
else
{
reminder = y % x;
if (reminder != 0) { reminder = reminder % x; }
}
}
Listing 3
4.
Now execute the Application and see
the result (Figure 1).
Intended
Result:
![New Picture.png]()
Figure 1
Summary:
In
this piece of writing, we have seen the implementation of The
Euclidean Algorithm. For writing the code here I used the C# Language.