欧几里得算法

数学与数论

说明

反复取余直到余数为零；最后非零值是最大公约数。

分析

gcd(a,b)=gcd(b,a mod b)，因为能同时整除 a 和 b 的数也能整除余数。每轮让第二个数变小，直到余数为零。

图解推演

48=2×18+12，18=1×12+6，12=2×6+0，因此最大公因数为 6。每次变换保留同一组公因数，非负余数严格变小保证终止。gcd(a,0)=|a|；若取绝对值遇到最小有符号整数，还需额外处理其不可表示的正值。

查看图表代码

适用前提与边界

它还能配合最小公倍数计算和分数约分；涉及负数时示例把最终结果转成非负。

示例输入与调用

fmt.Println(GCD(48, 18))

运行输出

6

完整 Go 示例

package main

import "fmt"

func GCD(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	if a < 0 {
		return -a
	}
	return a
}

func main() {
	fmt.Println(GCD(48, 18))
}