LCM(最小公倍数)和 GCD(最大公因数)在做ACM题时经常会用到,求两个整数的 LCM 和 GCD 有两种方法。
1. 辗转相除法(欧几里得算法)
-
定理:对于任意的两个整数 , 有 。( 表示 和 的最大公因数)
证明如下:
,其中q为整数, 。
设 ,则 , 。
则 ,进一步推出 。
故 也是 的因数,即 。
同理,设 ,则 ,, 。
则 。
故 也是 的因数, 即 。
综上,,原命题得证 。
所以要求两个数的最大公因数,只需根据递推式不断进行递推,并更新 , , 直到 为止,则此时的 即为 . 求得 以后,则 (最小公倍数)便可由 求得 。
2. 素因子分解
-
定理:任意一个正整数都能分解成若干个素数的幂的乘积的形式 .
证明略 。
由此可知,, . 其中 。
故