Saturday , 19 August 2017
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

Check Also

[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

One comment

  1. Awesome website to be followed for computer science

Leave a Reply to Anuja jamdade Cancel reply

Your email address will not be published. Required fields are marked *