求最大公约数（GCD）

辗转相除：大数对小数取余，余数为 0 时当前除数即答案。很好的循环+函数练习。

1. 完整例子

C
1#include <stdio.h>
2 
3int gcd(int a, int b) {
4 while (b != 0) {
5 int r = a % b;
6 a = b;
7 b = r;
8 }
9 return a;
10}
11 
12int main(void) {
13 printf("%d\n", gcd(48, 18)); // 6
14 printf("%d\n", gcd(17, 5)); // 1
15 return 0;
16}

2. 以 48 与 18 走一遍

  1. 48 % 18 = 12 → 变成 (18, 12)
  2. 18 % 12 = 6 → (12, 6)
  3. 12 % 6 = 0 → (6, 0) 结束，返回 6

3. 扩展

C
1/* 最小公倍数 = a*b / gcd(a,b)（注意先除后乘防溢出更稳） */
2int lcm(int a, int b) {
3 int g = gcd(a, b);
4 if (g == 0) return 0;
5 return a / g * b;
6}