Wednesday , 20 February 2019
Latest Posts
Home » ICSE Important Programs » Java program to find the GCD of two numbers (Division Method)

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

#### 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

## [Question 1] ISC 2017 Computer Practical Paper Solved – Box Packing

Solution of Program 1 of ISC 2017 Computer Science Paper 2 (Practical) Exam. Java program to input number of boxes to be packed and display the break-up of the cartons used in descending order of capacity