Java Reference
In-Depth Information
L
ISTING
4.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
12 System.out.print(
"Enter second integer: "
);
13
14
15
input
int
n1 = input.nextInt();
input
int
n2 = input.nextInt();
int
gcd =
1
;
// Initial gcd is 1
gcd
16
int
k =
2;
// Possible gcd
17
while
(k <= n1 && k <= n2) {
18
19 gcd = k;
// Update gcd
20 k++;
21 }
22
23 System.out.println(
"The greatest common divisor for "
+ n1 +
24
if
(n1 % k ==
0
&& n2 % k ==
0
)
check divisor
output
" and "
+ n2 +
" is "
+ gcd);
25 }
26 }
125
Enter first integer:
Enter second integer:
The greatest common divisor for 125 and 2525 is 25
2525
How would you write this program? Would you immediately begin to write the code? No.
It is important to
think before you type.
Thinking enables you to generate a logical solution for
the problem without concern about how to write the code. Once you have a logical solution,
type the code to translate the solution into a Java program. The translation is not unique. For
example, you could use a
for
loop to rewrite the code as follows:
think before you type
for
(
int
k =
2
; k <= n1 && k <= n2; k++) {
if
(n1 % k ==
0
&& n2 % k ==
0
)
gcd = k;
}
A problem often has multiple solutions, and the gcd problem can be solved in many ways.
Programming Exercise 4.14 suggests another solution. A more efficient solution is to use the
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:
multiple solutions
erroneous solutions
for
(
int
k =
2
; k <=
n1 /
2
&& k <=
n2 /
2
; k++) {
if
(n1 % k ==
0
&& n2 % k ==
0
)
gcd = k;
}
