最大公约数与最大公倍数算法

gcd和lcm算法

文章目录

• gcd和lcm算法
• • gcd算法
  • 二进制gcd算法
  • lcm算法
  • 参考

The greatest common divisor, abbreviated as gcd, is referred to as the highest shared factor. The least common multiple, often abbreviated as lcm, is known as the smallest number that is a multiple of both.

gcd算法

下面是欧几里得算法（Euclidean algorithm），也叫辗转相除法。

    int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    
    return gcd(b, a % b);
    }

二进制gcd算法

相较于计算余数的速度而言，在速度方面计算机能够快速进行减法运算、判断数值的奇偶性以及执行折半操作（通常采用位运算来实现）。该二进制GCD算法通过省略传统欧几里得算法中的取余操作来显著提升效率：

    #include <algor