计算输入值的最大公约数。


icon

输入/输出

  • ci32.png x —

    x是整数。

  • ci32.png y —

    y是整数。

  • ii32.png gcd(x,y) —

    gcd(x,y)返回x和y的最大公约数。

    • gcd(x,y)是x和y的最大公约数。

    要计算最大公约数gcd(x,y)，可先对x和y进行质数分解：

    x = Πi piai y = Πi pibi

    pi是x和y的所有质数因子。如pi未出现在分解中，相关指数为0。gcd(x,y)则定义为：

    gcd(x,y) = Πi pimin(ai , bi)

    例如，12和30的质数分解为：

    12 = 2² ×31 ×50 30 =21 ×31 ×51

    所以，

    gcd(12, 30) = 21 × 31 × 50 = 6