Java Program to Find GCD of two Numbers

Java Program to Find GCD of two Numbers

In this example, we will learn to find GCD of two numbers. 

The HCF or GCD of two integers is the largest integer that can exactly divide both numbers (without a remainder).

Example 1:Using for loop and if statement

public class GCD {

    public static void main(String[] args) {

        int n1 = 64, n2 = 160, gcd = 1;

        for(int i = 1; i <= n1 && i <= n2; ++i)
        {
            // Checks if i is factor of both integers
            if(n1 % i==0 && n2 % i==0)
                gcd = i;
        }

        System.out.printf("G.C.D of %d and %d is %d", n1, n2, gcd);
    }
}

Output :

G.C.D of 64 and 160 is 32

Here, two numbers whose GCD are to be found are stored in n1 and n2 respectively.

Then, a for loop is executed until i is less than both n1 and n2. This way, all numbers between 1 and smallest of the two numbers are iterated to find the GCD.

If both n1 and n2 are divisble by i, gcd is set to the number. This goes on until it finds the largest number (GCD) which divides both n1 and n2 without remainder.

 

Example 2: Using while loop and if else statement

public class GCD {

    public static void main(String[] args) {

        int n1 = 64, n2 = 160;

        while(n1 != n2)
        {
            if(n1 > n2)
                n1 -= n2;
            else
                n2 -= n1;
        }

        System.out.println("G.C.D = " + n1);
    }
}

Output :

G.C.D = 32