Java program to find the greatest common divisor of two numbers

Java Comprehensive Examples

In this program, you will learn how to find the greatest common divisor (GCD) of two numbers in a Java program. This is done by using for and while loops with the help of if-else statements.

The HCF or GCD of two integers can be the largest integer that can exactly divide the two numbers (with no remainder).

Example1：Use for loop and if statement to find the greatest common divisor of two numbers

public　class　GCD　{
　　　　public　static　void　main(String[]　args)　{
　　　　　　　　int　n1　=　81,　n2　=　153, gcd =　1;
　　　　　　　　for(int i =　1; i <= n1　&& i <= n2;　++i)
　　　　　　　　{
　　　　　　　　　　　　//　Check if i is a factor of two integers
　　　　　　　　　　　　if(n1　%i == 0 && n2　%i == 0)
　　　　　　　　　　　　　　　　gcd = i;
　　　　　　　　}
　　　　　　　　System.out.printf("%d and %d have the greatest common divisor %d", n1,　n2, gcd);
　　　　}
}

The output when running the program is:

81　And　153　The greatest common divisor of　9

Here, the two numbers for which the greatest common divisor will be found are stored in n1and n2Among them.

Then, execute a for loop until i is less than n1and n2End. In this way, the iteration1To find the greatest common divisor by considering all numbers between the two smallest numbers.

If n1and n2If a number can be divided by i, then set gcd to the number. Continue doing this until the largest number (GCD) is found, which will be equal to n1and n2are divided without a remainder.

We can also solve this problem using a while loop, as shown below:

Example2：Using while loop and if else statements to find the GCD of two numbers

public　class　GCD　{
　　　　public　static　void　main(String[]　args)　{
　　　　　　　　int　n1　=　81,　n2　=　153;
　　　　　　　　while(n1　!=　n2)
　　　　　　　　{
　　　　　　　　　　　　if(n1　>　n2)
　　　　　　　　　　　　　　　　n1　-=　n2;
　　　　　　　　　　　　else
　　　　　　　　　　　　　　　　n2　-=　n1;
　　　　　　　　}
　　　　　　　　System.out.println("G.C.D　= ")　+　n1);
　　　　}
}

The output when running the program is:

G.C.D　=　9

This is a better way to find the GCD. In this method, subtract the smaller integer from the larger integer and then assign the result to the variable that stores the larger integer. This process continues until n1and n2are equal.

Only when the user inputs a positive integer can the above two programs work as expected. This is a modification of the second example, which can find the GCD of positive and negative integers.

Example3：Positive and negative numbers are GCD

public　class　GCD　{
　　　　public　static　void　main(String[]　args)　{
　　　　　　　　int　n1　=　81,　n2　=　-153;
　　　　　　　　n1　=　(　n1　>　0)　?　n1　:　-n1;
　　　　　　　　n2　=　(　n2　>　0)　?　n2　:　-n2;
　　　　　　　　while(n1　!=　n2)
　　　　　　　　{
　　　　　　　　　　　　if(n1　>　n2)
　　　　　　　　　　　　　　　　n1　-=　n2;
　　　　　　　　　　　　else
　　　　　　　　　　　　　　　　n2　-=　n1;
　　　　　　　　}
　　　　　　　　System.out.println("G.C.D　= ")　+　n1);
　　　　}
}

The output when running the program is:

G.C.D　=　9

Java Comprehensive Examples