最大公约数和最小公倍数（Greatest Common Divisor and Least Common Multiple）

2024-07-15 15:38| 来源: 网络整理| 查看: 265

定义：

最大公约数（英语：greatest common divisor，gcd）。是数学词汇，指能够整除多个整数的最大正整数。而多个整数不能都为零。例如8和12的最大公因数为4。

最小公倍数是数论中的一个概念。若有一个数$$X$$，可以被另外两个数$$A$$、$$B$$整除，且$$X$$大于（或等于）$$A$$和$$B$$，则$$X$$X为$$A$$和$$B$$的公倍数。$$A$$和$$B$$的公倍数有无限个，而所有的公倍数中，最小的公倍数就叫做最小公倍数。两个整数公有的倍数称为它们的公倍数，其中最小的一个正整数称为它们两个的最小公倍数。

辗转相除法：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，252和105的最大公约数是21 $$ (252=21\times 12;105=21\times 5)$$因为 252 − 105 = 21 × (12 − 5) = 147 ，所以147和105的最大公约数也是21。在这个过程中，较大的数缩小了，所以继续进行同样的计算可以不断缩小这两个数直至其中一个变成零。这时，所剩下的还没有变成零的数就是两数的最大公约数。

运用辗转相除法来计算最大公约数和最小公倍数 #include int main() { int a, b; printf("请输入两个数：\n"); scanf("%d%d", &a, &b); int x = a, y = b; while (b != 0) { int temp = a % b; a = b; b = temp; } printf("最大公约数：%d\n", a); printf("最下公倍数：%d\n", x * y / a); return 0; } 使用自定义函数来计算最大公约数和最小公倍数 int GCD(int a, int b) { if (b) while ((a %= b) && (b %= a)); return a + b; } int LCM(int a, int b) { return a * b / GCD(a, b); }

【本文地址】

公司简介

联系我们