Java program to find the GCD of two numbers (Division Method)

Write a Program in Java to input 2 numbers and find their Greatest Common Divisor (GCD).

Note: If the 2 numbers are 54 and 24, then the divisors (factors) of 54 are: 1, 2, 3, 6, 9, 18, 27, 54.

Similarly the divisors (factors) of 24 are: 1, 2, 3, 4, 6, 8, 12, 24.

The numbers that these two lists share in common are the common divisors (factors) of 54 and 24: 1, 2, 3, 6.

The greatest (highest) of these is 6. That is the greatest common divisor or the highest common factor of 54 and 24.

Calculating HCF / GCD by Prime Factorisation Method is long and more time-consuming, and due to these disadvantages new method was evolved by Mathematician namely, Successive Division Method

Under Successive Division Method, HCF / GCD = The Last Divisor of the given numbers .

Following example can guide you How to calculate HCF / GCD by Successive Division Method ?

Example : By using Successive Division Method, find the GCD of 24 & 18 ?

Answer : Steps and the way of finding GCD by Successive Division Method is as :-

Step 1 = Divide the larger number 24 by the smaller number 18. And this division will give remainder 6.
Step 2 = Now, divide 18 (divisor of step 1) with 6 (remainder of step 1)
Step 3 = Division in Step 2 give us remainder 0 (Zero). And The Last Divisor is the GCD of 24 & 18.
Hence, GCD = 6

18 | 24 | 1                      18    ______                     6 | 18 | 3                     18         ______              0 import java.util.*; class Gcd     {         public static void main(String args[])throws Exception         {             Scanner sc = new Scanner(System.in);             System.out.print("Enter the First no : ");             int n1=sc.nextInt();             System.out.print("Enter the Second no : ");             int n2=sc.nextInt();             int r;                           while(n2 != 0)             {                 r = n1 % n2;                 n1 = n2;                 n2 = r;             }             System.out.print("GCD = "+n1);         }     } import java.util.*; class Gcd     {         public static void main(String args[])throws Exception         {             Scanner sc = new Scanner(System.in);             System.out.print("Enter the First no : ");             int n1=sc.nextInt();             System.out.print("Enter the Second no : ");             int n2=sc.nextInt();                           while(n1 != n2)             {                 if(n1 > n2)                     n1 = n1-n2;                 else                     n2 = n2-n1;             }             System.out.print("GCD = "+n1);         }     }