LOOPS - Introduction to Java Programming: Comprehensive Version - page 180

L ISTING 5.9

GreatestCommonDivisor.java
1 import java.util.Scanner;
2
3 public class GreatestCommonDivisor {
4 /** Main method */
5 public static void main(String[] args) {
6 // Create a Scanner
7 Scanner input = new Scanner(System.in);
8
9 // Prompt the user to enter two integers
10 System.out.print( "Enter first integer: " );
11 int n1 = input.nextInt();
12 System.out.print( "Enter second integer: " );
13

input

input

int n2 = input.nextInt();

14
15 int gcd = 1 ; // Initial gcd is 1
16 int k = 2; // Possible gcd
17 while (k <= n1 && k <= n2) {
18 if (n1 % k == 0 && n2 % k == 0 )
19 gcd = k; // Update gcd
20 k++;
21 }
22
23 System.out.println( "The greatest common divisor for " + n1 +
24

gcd

check divisor

output

" and " + n2 + " is " + gcd);

25 }
26 }

Enter first integer: 125
Enter second integer: 2525
The greatest common divisor for 125 and 2525 is 25

Translating a logical solution to Java code is not unique. For example, you could use a for
loop to rewrite the code as follows:

for ( int k = 2 ; k <= n1 && k <= n2; k++) {
if (n1 % k == 0 && n2 % k == 0 )
gcd = k;
}

multiple solutions

A problem often has multiple solutions, and the gcd problem can be solved in many ways.
Programming Exercise 5.14 suggests another solution. A more efficient solution is to use the
classic Euclidean algorithm (see Section 22.6).
You might think that a divisor for a number n1 cannot be greater than n1 / 2 and would
attempt to improve the program using the following loop:

erroneous solutions

for ( int k = 2 ; k <= n1 / 2 && k <= n2 / 2 ; k++) {
if (n1 % k == 0 && n2 % k == 0 )
gcd = k;
}