c++ - 如何去掉两个数的公约数

Question

所以我有一个函数可以除以一对数字，直到它们不再有公约数:

void simplify(int &x, int &y){
    for (int i = 2;;++i){
        if (x < i && y < i){
            return;
        }
        while (1){
            if (!(x % i) && !(y % i)){
                x /= i;
                y /= i;
            } else {
                break;
            }
        }
    }
}

如何提高效率？我知道这个解决方案中的一个问题是它测试复合数的可除性，当它到达它们时它不会有任何它的因素，所以它只是浪费了计算。如果程序事先不知道一组素数/在函数运行时计算它们，我可以这样做吗？

Answer 1

使用the Euclidean algorithm ¹:

1. 令 a 为两个给定正整数中较大的一个，b 为较小的一个。
2. 令 r 为 a 除以 b 的余数。
3. 如果 r 为零，我们就完成了，b 是最大公约数。
4. 否则，让a取b的值，让b取r的值，并且转到第 2 步。

一旦你有了最大公约数，你就可以将原来的两个数除以它，这将产生两个比率相同但没有大于一的公因数的数。

引用

¹ 欧几里得，元素，第七册，命题 1 和命题 2，大约公元前 300 年。

注意事项

欧几里得用的是减法，这里改成了余数。

一旦该算法起作用，您可能会考虑稍微复杂一点的 Binary GCD ，用减法和位运算代替除法(在某些处理器上速度很慢)。