The Euclidean algorithm finds the greatest common divisor of two numbers by replacing the pair with the smaller number and the remainder, over and over.
Strategy
Decrease and conquer
Swap the pair for a smaller pair with the same answer, until one of them is zero.
- Reduce: take the remainder of the larger number divided by the smaller.
- Slide: the smaller number becomes the new first, the remainder the new second.
- Stop: when the remainder is zero, the number in hand is the answer.
Press Cut to slice the biggest square you can off the rectangle. When the last cut leaves nothing behind, that square's side is the greatest common divisor.
Purpose
Find the largest number that divides two others exactly.
Input
Two int values.
Output
Their greatest common divisor.
Constraints
- Use numbers that are zero or more. A negative input hands back a negative divisor.
- GCD(
0,0) comes back as0, which is worth guarding. LCMdivides before it multiplies, which keeps the result from overflowing.
How the Euclidean algorithm works
The Euclidean algorithm finds the largest number that divides two others exactly. That number is called the greatest common divisor.
Picture a rectangle 48 wide and 18 tall, and try to tile it with identical squares. Cut off the biggest square you can, twice, and an 18 by 12 rectangle is left. Do it again and you have 12 by 6. Cut two 6 by 6 squares and nothing is left over, so 6 is the biggest square that tiles the original.
It is over two thousand years old and still what your computer runs when it reduces a fraction, lines up two repeating schedules, or picks keys in cryptography.
What the algorithm keeps track of
| Name | Type | What it is for |
|---|---|---|
| a | int | The larger number, and where the answer ends up. |
| b | int | The smaller number. Hits zero when the work is done. |
| a % b | int | What is left over after taking b out of a as many times as it goes. |
Walk through it
1 Start with two whole numbers
Order does not matter. If you pass the smaller one first, the first pass simply swaps them.
a, b := 48, 182 Take the remainder
Divide the bigger by the smaller and keep only what is left over. 18 goes into 48 twice with 12 to spare.
a % b // 48 % 18 = 123 Slide the pair along
The old smaller number becomes the new bigger one, and the remainder becomes the new smaller one. Go's multiple assignment does both at once.
a, b = b, a%b // a=18, b=124 Repeat until nothing is left over
Each pass shrinks the numbers, so a remainder of zero always arrives.
for b != 0 {
a, b = b, a%b
}
// 48,18 -> 18,12 -> 12,6 -> 6,05 Read the answer from a
When b reaches zero, a is holding the greatest common divisor.
return a // 6The whole program
Put it together and you get the greatest common divisor, plus the lowest common multiple almost for free.
package main
import "fmt"
// GCD returns the largest number that divides both a and b.
func GCD(a, b int) int {
for b != 0 {
a, b = b, a%b
}
return a
}
// LCM divides before multiplying, which keeps the number from overflowing.
func LCM(a, b int) int {
return a / GCD(a, b) * b
}
func main() {
fmt.Println(GCD(48, 18))
fmt.Println(GCD(270, 192))
fmt.Println(GCD(13, 7))
fmt.Println(LCM(4, 6))
}$ go run main.go
6
6
1
12A result of 1, as with 13 and 7, means the two numbers share no factor at all.