输入 2 个正整数 m 和 n ,求其最大公约数和最小公倍数;
时间: 2024-03-24 20:32:19 浏览: 58
C语言113题
输入两个正整数 m 和 n,求它们的最大公约数和最小公倍数。
最大公约数(Greatest Common Divisor,简称GCD)是指能够同时整除两个数的最大正整数,最小公倍数(Least Common Multiple,简称LCM)是指能够同时被两个数整除的最小正整数。
计算最大公约数和最小公倍数的方法有多种,以下是其中两种常见的方法:
1.辗转相除法:假设 m > n,则用 m 除以 n,得到余数 r1,再用 n 除以 r1,得到余数 r2,以此类推,直到余数为 0 为止,此时的除数即为最大公约数,最小公倍数为 m*n/最大公约数。
2.质因数分解法:将 m 和 n 分别分解质因数,然后将它们的公共质因数乘起来,得到最大公约数,将 m 和 n 的所有质因数乘起来,再除以最大公约数,得到最小公倍数。
阅读全文