如何去掉2个数的公约数

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

听起来像是C++17库特性gcd的工作。

#include <numeric>
void simplify(int &x, int &y)
{
    const auto d = std::gcd(x, y);
    x /= d;
    y /= d;
}

Compiler Explorer