- 最大公约数
- 方法一
- 方法二
- 最小公倍数
- 方法一
- 方法二
- 方法三
最大公因数 也称最大公约数、最大公因子,指两个或多个整数共有约数中最大的一个。简单的说就是两数能同时被同一个数,除尽没有余数的,同时那个数是除尽中最大的数。
比如48和36
48=2x2x2x2x3
36=2x2x3x3
其中48和36中都出现2x2x3;
所以48和36的大公约数为12.
思路 :两个数的最大公约数是能把两个一大一小的两个数除尽,最大的除数也是两个数中最大的数,因此用条件操作符(n > m ? n : m)求出最大的数,作为除数,然后依次减减,但要打于0,作为条件放在循环中。
int main() { int n = 0; int m = 0; scanf("%d %d", &n, &m); int mum = (n > m ? n : m); while (mum >0) { if (n % mum == 0 && m % mum == 0) { break; } mum--; } printf("%d", mum); return 0; }方法二
辗转相除法
- 辗转相除法是求两个自然数的最大公约数的一种方法,也叫欧几里德算法。
- 用较大数除以较小数,再用出现的余数去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。最后为0,则除数为最大公约数。
我原理也不是很清楚只知道是如此算到的。然后在看看上面的图,懂计算的步骤。
代码演示
int main() { int m = 0; int n = 0; scanf("%d %d", &m, &n); int c = 0; //用来存放余数 while (m % n != 0) { c = m % n; m = n; n = c;//最大公约数会落在n上 } printf("%d", n); return 0; }最小公倍数
最小公倍数 :公倍数(common multiple)指在两个或两个以上的自然数中,如果它们有相同的倍数,这些倍数就是它们的公倍数,其中除0以外最小的一个公倍数,叫做这几个数的最小公倍数。
思路 :两个数的最小倍数也是比两个数的最大的数还要大,因此用条件操作符(n > m ? n : m)求出最大的数,作为被除数,然后依次加加,找到后跳出循环。
代码演示
int main() { int n = 0; int m = 0; scanf("%d %d", &n, &m); int e = (n > m ? n : m); while (e>0) { if (e % n == 0 && e % m == 0) break; e++; } printf("%d ", e); return 0; }方法二
公式:两个数的乘积(m * n) / 最大公约数
int main() { int m = 0; int n = 0; scanf("%d %d", &m, &n); int c = 0; int a = m; int b = n; while (a % b != 0) { c = a % b; a = b; b = c; } printf("%d", m*n/b); return 0; }方法三
思路 :如果一个数乘于一个变量 i 还能被另一个数整除,那这个数(n * i)一定是着两个数的最小公倍数。
int main() { int n = 0; int m = 0; scanf("%d %d", &n, &m); int i = 1; while (n * i % m != 0) { i++; } printf("%d ", n * i); return 0; }