输入两个正整数 m 和 n,求其最大公约数和最小公倍数
时间: 2023-11-03 10:44:51 浏览: 444
C语言113题
最大公约数可以使用辗转相除法来求解。该方法的基本思想是:两个数 a,b (a>b)的最大公约数等于a除以b的余数c和b之间的最大公约数。具体实现方法为:设m,n为两个正整数,r为m mod n(即m除以n的余数),那么最大公约数 gcd(m,n) = gcd(n,r) 。重复这个过程,直到r=0,此时n就是最大公约数。
最小公倍数可以用下面这个公式来求: lcm(m,n) = m * n / gcd(m,n)
阅读全文