Course navigation & on this page
Euclidean algorithm
Find the greatest common divisor by repeatedly taking a remainder.
Overview
Find the greatest common divisor by repeatedly taking a remainder. Each remainder reduces the pair while preserving the common divisors. The number of remainder operations is logarithmic for positive inputs. This assumes unit-cost integer arithmetic.
Step-by-step walkthrough
- Read nonnegative integers p and q.
- If q is zero, return p.
- Replace (p, q) by (q, p % q).
- Repeat until the second value becomes zero.
Complexity analysis
| Best case | Θ(1) |
|---|---|
| Average / aggregate | Input-dependent |
| Worst case | O(log min(p, q)) |
| Space | O(1) iterative; O(log min(p, q)) recursive |
Each remainder reduces the pair while preserving the common divisors. The number of remainder operations is logarithmic for positive inputs. This assumes unit-cost integer arithmetic.
A worked example
(48, 18) → (18, 12) → (12, 6) → (6, 0). The answer is 6.
Remainder trace
gcd(48, 18)
| Call | p | q | p mod q |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
Replace (48, 18) with (18, 12).
Common mistake / implementation note
The supplied code can return a negative value for negative inputs. It does not validate the argument count.
The supplied code can return a negative value for negative inputs. It does not validate the argument count.
Original course code
Source: code/Euclid.java. Original logic, comments, variable names and attribution are retained.
Download Euclid.javaEuclid.javaJAVA
/******************************************************************************
* 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 either p or q 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;
}
// main method
public static void main(String[] args) {
int p = Integer.parseInt(args[0]);
int q = Integer.parseInt(args[1]);
int d = gcd(p, q); //resursion
int d2 = gcd2(p, q); //while loop
System.out.println("gcd(" + p + ", " + q + ") = " + d);
System.out.println("gcd(" + p + ", " + q + ") = " + d2);
}
}