Euclid Algorithm
Learn how to write code to find the GCD using Euclid's algorithm.
We'll cover the following...
Euclid’s algorithm is one of the oldest algorithms still relevant today, not only in discrete mathematical conceptions but also in the computational world of 1s and 0s.
About a thousand years ago, Greek mathematicians used Euclid’s algorithm to find the greatest common divisors of two numbers. Originally, it was subtraction based; later, the same algorithm was written in numerous ways, remodeling the original one.
Note: Euclid of Alexandria was referred to as the “father of geometry.”
Java implementation of the Euclid’s algorithm
Let’s take a quick look at the original Euclid’s algorithm in a Java program, as shown in the following code:
import java.util.Scanner;
//Euclid’s Algorithm
class Main{
static int numOne = 0;
static int numTwo = 0;
//this is Euclid's original version
static int subtractionBased(int numOne, int numTwo){
while (numOne != numTwo){
if(numOne > numTwo)
numOne = numOne - numTwo;
else
numTwo = numTwo - numOne;
}
return numOne;
}
public static void main(String[] args) {
System.out.println("Enter a number: ");
Scanner num1 = new Scanner(System.in);
numOne = num1.nextInt();
System.out.println("Enter another number: ");
Scanner num2 = new Scanner(System.in);
numTwo = num2.nextInt();
System.out.println("You have entered " + numOne + " and " + numTwo);
System.out.println("The GCD is: " + subtractionBased(numOne, numTwo));
}
}Java code for Euclid's algorithm
We can take any ...