**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]:**

/** * The class Gcd inputs two numbers and finds their Gcd * @author : www.guideforschool.com * @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]:**

/** * The class Gcd inputs two numbers and finds their Gcd * @author : www.guideforschool.com * @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

Awesome website to be followed for computer science