C语言求最大公约数及最小公倍数.pdf
需积分: 0 189 浏览量
2023-10-18
08:57:58
上传
评论 1
收藏 116KB PDF 举报
C语⾔求最⼤公约数及最⼩公倍数
C语⾔求最⼤公约数及最⼩公倍数
1. 最⼤公约数
1.1 定义
最⼤公约数（Greatest Common Divisor，GCD），也称最⼤公因数、最⼤公因⼦，是⼀种数学概念，指两个或多个整数共有约数中最
⼤的⼀个。
1.2 解法⼀：常规法（暴⼒法）
1.2.1 定义
由于最⼤公约数的本质是⼀个最⼤的能同时被两整数整除的⾃然数。所以我们先⽐较两数⼤⼩，从较⼤数开始向上递增，直到找到那个最⼩
公倍数。
1.2.2 代码实现
int gcd4(int a, int b)
{
//
⾸先找到两个数中较⼤的数，⽤
a
存储较⼤数
if (a < b)
{
int temp = a;
a = b;
b = temp;
}
//
从较⼤数开始寻找符合条件的最⼤公约数
for (int i = a; i > 0; --i)
{
if (a % i == 0 && b % i == 0)
{
return i;
}
}
}
1.3 解法⼆：辗转相除法（欧⼏⾥德法）
1.3.1⽅法解释：
⽤较⼤数除以较⼩数，再⽤出现的余数（第⼀余数）去除除数，再⽤出现的余数（第⼆余数）去除第⼀余数，如此反复，直到最后余数是0
为⽌。如果是求两个数的最⼤公约数，那么最后的除数就是这两个数的最⼤公约数。
1.3.2实例：
例如，求（319，377）：
∵ 319÷377=0（余319）
∴（319，377）=（377，319）；
∵ 377÷319=1（余58）
∴（377，319）=（319，58）；
∵ 319÷58=5（余29）
∴ （319，58）=（58，29）；
∵ 58÷29=2（余0）
资源评论
