The
greatest common divisor (gcd) of two positive
integers is the largest integer that divides evenly into
both of them. For example, the greatest common divisor
of 102 and 68 is 34 since both 102
and 68 are multiples of 34, but no integer larger than 34 divides evenly
into 102 and 68.
We can efficiently compute the gcd using the following property,
which holds for positive integers
p and
q:
If p > q, the gcd of p and
q is the same as the gcd
of q and p % q.
The static method
gcd() in
Euclid.java
is a compact recursive function whose reduction
step is based on this property.
gcd(1440, 408)
gcd(408, 216)
gcd(216, 192)
gcd(192, 24)
gcd(24, 0)
return 24
return 24
return 24
return 24
return 24
Euclid.java
/*************************************************************************
* Compilation:
javac Euclid.java
* Execution:
java Euclid p q
*
* Reads two command-line arguments p and q and
computes the greatest
* common divisor of p and q using Euclid's
algorithm.
*
* Remarks
* -----------
* - may return the negative of the gcd if p
is negative
*
*************************************************************************/
public class Euclid {
// recursive
implementation
public
static int gcd(int p, int q) {
if (q ==
0) return p;
else
return gcd(q, p % q);
}
//
non-recursive implementation
public
static int gcd2(int p, int q) {
while (q
!= 0) {
int
temp = q;
q =
p % q;
p =
temp;
}
return
p;
}
public
static void main(String[] args) {
int p =
Integer.parseInt(args[0]);
int q =
Integer.parseInt(args[1]);
int
d = gcd(p, q);
int d2 =
gcd2(p, q);
System.out.println("gcd(" + p + ", " + q + ") =
" + d);
System.out.println("gcd(" + p + ", " + q + ") =
" + d2);
}
}
Copyright ©
2000–2010, Robert Sedgewick and Kevin Wayne.
Last updated: Wed Feb 9 09:05:37 EST 2011.
