Tuesday, 18 July 2017 06:27

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

Written by
Rate this item
(1 Vote)

#### Question:

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`

#### Programming Code [Method 1]:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 `/**` `* The class Gcd inputs two numbers and finds their Gcd` `* @author : www.anishsir.in` `* @Program Type : BlueJ Program - Java` `*/`   `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);` `        ``}` `    ``}`

#### Programming Code [Method 2]:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 `/**` `* The class Gcd inputs two numbers and finds their Gcd` `* @author : www.anishsir.in` `* @Program Type : BlueJ Program - Java` `*/`   `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);` `        ``}` `    ``}`

#### Output:

Enter the First no : 54
Enter the Second no : 24
GCD = 6 