Simple Java plan to discovery GCD (Greatest mutual Divisor) or GCF
(Greatest Common Factor) or HCF (Highest mutual factor). The GCD of 2 numbers is the largest positive integer that divides both the numbers fully i.e. without whatsoever remainder. There are multiple methods to discovery GCD , GDF or HCF of 2 numbers but
Euclid's algorithm is really pop in addition to slow to understand, of course, only if you lot empathize
how recursion works. Euclid's algorithm is an efficient way to discovery GCD of 2 numbers in addition to it's pretty slow to implement using recursion inwards Java program. According to Euclid's method GCD of 2 numbers a, b is equal to
GCD(b, a modern b) in addition to
GCD(a, 0) = a. The afterwards instance is the base of operations instance of our Java plan to discovery GCD of 2 numbers using recursion. You tin every bit good calculate greatest mutual divisor inwards Java without using recursion but that would non endure every bit slow every bit the recursive version, but nonetheless a practiced exercise from coding interviews indicate of view.
It's really slow to empathize this algorithm in i lawsuit you lot hold off at the menstruation chart, which explains how Euclid's GCD algorithm works. You tin every bit good read
Introduction to Algorithm past times Thomas Cormen to acquire to a greater extent than most similar figurer algorithms. This is i of the most pop books to acquire Data construction in addition to algorithms in addition to widely used every bit textbooks for algorithms inwards many school, colleges, in addition to universities. It is every bit good popularly known every bit CLRS (Cormen, Leiserson, Rivest, Stein).
In Euclid's algorithm, nosotros start amongst 2 numbers
X in addition to
Y. If Y is null hence greatest mutual divisor of both volition endure X, but if Y is non null hence nosotros assign the
Y to
X in addition to
Y becomes
X%Y. Once in i lawsuit again nosotros banking concern represent if Y is zero, if yeah hence nosotros cause got our greatest mutual divisor or GCD otherwise nosotros hold kicking the bucket along similar this until Y becomes zero. Since nosotros are using modulo operator, the publish is getting smaller in addition to smaller at each iteration, hence the X%Y volition eventually acquire zero.
Let' accept an illustration of calculating GCD of 54 in addition to 24 using Euclid's algorithm. Here X = 54 in addition to Y = 24, since Y is non null nosotros motion to the logical component in addition to assign X = Y, which agency X becomes 24 in addition to Y becomes
54%24 i.e 6. Since Y is nonetheless non zero, nosotros in i lawsuit again apply the logic. This times X volition acquire 6 in addition to Y volition acquire
24%6 i.e. Y=0. Bingo, Y is at in i lawsuit null which agency nosotros cause got our reply in addition to it's cypher but the value of X which is 6 (six).
The algorithm volition acquire clearer when you lot run across the menstruation nautical chart of calculating GCD of 2 numbers using recursion every bit shown below. You tin run across nosotros are starting amongst 2 numbers X and Y in addition to if Y=0 hence nosotros got our answer, otherwise, nosotros apply logic in addition to banking concern represent again. Now let's acquire how to convert Euclid's algorithm to discovery GCD into Java code.
Here is my consummate code illustration of how to discovery GCD of 2 numbers inwards Java. This Java plan uses
Euclid's method to discovery GCD of 2 numbers. Thy must endure an integer, hence brand certain you lot banking concern represent the numbers entered past times user e.g. floating indicate numbers are non allowed.
Similarly, whatsoever alphabets in addition to other characters are non allowed except '+' in addition to '-' sign in addition to all these rules are ensured by
Scanner.nextInt() call. This method volition throw an fault if the user volition acquire into an invalid value instead of an integer.
Java Program to calculate GCD of 2 numbers /** * Java plan to demonstrate How to discovery Greatest Common Divisor or GCD of * 2 numbers using Euclid’s method. There are other methods every bit good to * discovery GCD of 2 publish inwards Java but this illustration of finding GCD of 2 publish * is most simple. * * @author Javin Paul */ public class GCDExample { public static void main(String args[]){ //Enter 2 publish whose GCD needs to endure calculated. Scanner scanner = new Scanner(System.in); System.out.println("Please acquire into starting fourth dimension publish to discovery GCD"); int number1 = scanner.nextInt(); System.out.println("Please acquire into minute publish to discovery GCD"); int number2 = scanner.nextInt(); System.out.println("GCD of 2 numbers " + number1 +" in addition to " + number2 +" is :" + findGCD(number1,number2)); } /* * Java method to discovery GCD of 2 publish using Euclid's method * @return GDC of 2 numbers inwards Java */ private static int findGCD(int number1, int number2) { //base case if(number2 == 0){ return number1; } return findGCD(number2, number1%number2); } } Output: Please acquire into starting fourth dimension publish to discovery GCD 54 Please acquire into minute publish to discovery GCD 24 GCD of 2 numbers 54 in addition to 24 is :6 That’s all on
how to discovery GCD of 2 numbers inwards Java. You tin role this Java plan to arrive at for viva or other figurer homework in addition to assignment show or for your self-practice to amend programming inwards Java. BTW, in that place are a duet of other technique to discovery Greatest mutual divisor inwards Java, every bit an exercise you lot tin explore those methods in addition to write code for that. The fundamental indicate is you lot ask to acquire how to convert an algorithm into code to acquire a programmer.
