C 的 GCD 函数

Q 1. 问题5（可整除） 我尝试了蛮力法，但是需要时间，所以我参考了几个网站，找到了这段代码：

#include<stdio.h>
int gcd(int a, int b)
{
    while (b != 0)
    {
        a %= b;
        a ^= b;
        b ^= a;
        a ^= b;
    }

    return a;
}

int lcm(int a, int b)
{
    return a / gcd(a, b) * b;
}

int main()
{
    int res = 1;
    int i;
    for (i = 2; i <= 20; i++)
    {
        res = lcm(res, i);
    }

    printf("%d\n", res);
    return 0;
}

这很简单，但我不明白函数“gcd”是如何工作的；有人可以帮我理解其中的逻辑吗？ （我知道它返回 2 个数字的 GCD，但为什么要进行这么多操作？）

对于你的第二个问题：GCD 函数使用欧几里得算法 http://en.wikipedia.org/wiki/Euclidean_algorithm。它计算A mod B，然后用 a 交换 A 和 BXOR swap http://en.wikipedia.org/wiki/XOR_swap_algorithm。更具可读性的版本可能如下所示：

int gcd(int a, int b)
{
    int temp;
    while (b != 0)
    {
        temp = a % b;

        a = b;
        b = temp;
    }
    return a;
}