分解质因数法求两个数 的最大公约数C++代码

以下是使用分解质因数法求解两个数最大公约数的Python代码：

def prime_factors(n):
    """返回n的所有质因子"""
    factors = []
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

def gcd(a, b):
    """返回a和b的最大公约数"""
    a_factors = prime_factors(a)
    b_factors = prime_factors(b)
    gcd_factors = []
    for factor in a_factors:
        if factor in b_factors:
            gcd_factors.append(factor)
            b_factors.remove(factor)
    if gcd_factors:
        return reduce(lambda x, y: x*y, gcd_factors)
    else:
        return 1

使用`prime_factors`函数分别获取a和b的质因子，然后将两个列表中相同的因子添加到`gcd_factors`列表中，最后将`gcd_factors`中的所有元素乘积作为结果返回。如果没有相同质因子，则最大公约数为1。