最大公约数(GCD)的两种 C 语言实现
一、辗转相除法(欧几里得算法) 数学原理 定理: gcd(a, b) = gcd(b, a % b),其中 a ≥ b。 证明: 设 a = k * b + r(其中 k = a / b,r = a % b),则: 若 d 能整除 a 和 b,则 d 也能整除 r = a - k * b 若 d 能整除 b 和 r,则 d 也能整除 a = k * b + r 因此 (a, b) 和 (b, a % b) 的公约数完全相同,最大公约数也相同。不断递归直到余数为 0,此时的除数即为 GCD。 ...