Java Reference
In-Depth Information
Note
The Big
O
notation provides a good theoretical estimate of algorithm efficiency. How-
ever, two algorithms of the same time complexity are not necessarily equally efficient.
As shown in the preceding example, both algorithms in Listings 5.9 and 22.3 have the
same complexity, but in practice the one in Listing 22.3 is obviously better.
A more efficient algorithm for finding the GCD was discovered by Euclid around 300 b.c.
This is one of the oldest known algorithms. It can be defined recursively as follows:
Let
gcd(m, n)
denote the GCD for integers
m
and
n
:
practical consideration
Euclid's algorithm
If
m % n
is
0
,
gcd (m, n)
is
n
.
■
Otherwise,
gcd(m, n)
is
gcd(n, m % n)
.
■
It is not difficult to prove the correctness of this algorithm. Suppose
m % n = r
. Thus,
m =
qn + r
, where
q
is the quotient of
m / n
. Any number that is divisible by
m
and
n
must also
be divisible by
r
. Therefore,
gcd(m, n)
is the same as
gcd(n, r)
, where
r = m % n
. The
algorithm can be implemented as in Listing 22.4.
L
ISTING
22.4
GCDEuclid.java
1
import
java.util.Scanner;
2
3
public class
GCDEuclid {
4
/** Find GCD for integers m and n */
5
public static int
gcd(
int
m,
int
n) {
6
if
(m % n ==
0
)
base case
7
return
n;
8
else
9
return
gcd(n, m % n);
reduction
10 }
11
12
/** Main method */
13
public static void
main(String[] args) {
14
// Create a Scanner
15 Scanner input =
new
Scanner(System.in);
16
17
// Prompt the user to enter two integers
18 System.out.print(
"Enter first integer: "
);
19
int
m = input.nextInt();
20 System.out.print(
"Enter second integer: "
);
21
input
int
n = input.nextInt();
input
22
23 System.out.println(
"The greatest common divisor for "
+ m +
24
" and "
+ n +
" is "
+ gcd(m, n));
25 }
26 }
Enter first integer: 2525
Enter second integer: 125
The greatest common divisor for 2525 and 125 is 25
Enter first integer: 3
Enter second integer: 3
The greatest common divisor for 3 and 3 is 3
Search WWH ::
Custom Search