c语言求大公约数_c语言编程求最小公倍数
正整数a和b的最大公约数,我们用符号p表示,即:(a,b)=p;它们的最小公倍数,我们用符号q表示,即:[a,b]=q。
示例1:求24和30的最大公约数及最小公倍数。
解答:对于较为简单的数字,我们可以直接使用短除法来寻找它们的公因数:
1) 用24和30的公因数2分别去除,得到商12和15;
2) 接着,用12和15的公因数3再次去除,商变为4和5;
3) 4和5已经没有其他公因数了,短除法结束。
由于2和3的乘积为6,因此24和30的最大公约数为:(24, 30) = 6。
再来看所有公因数以及最后商的乘积:2×3×4×5 = 120,
24和30的最小公倍数为:[24, 30] = 120。
示例2:求221和493的最大公约数及最小公倍数。
解答:对于不易直接观察出公因数的数字,我们可以使用辗转相除法:
- 用较大的数493除以较小的数221,得到商2,余数为51;
- 然后,将上面的除数221作为新的被除数,余数51作为新的除数再次相除,得到商4,余数为17;
- 再次以51为被除数,以17为除数相除,得到商3,此时余数为0。
当余数为0时,倒数第二个余数17就是这两个数的最大公约数,所以(221, 493) = 17。
由于两个数的最大公约数与最小公倍数的乘积等于这两个数的乘积,即pq = ab。最小公倍数q可以通过ab除以最大公约数p来计算,[221, 493] = 221 × 493 / 17 = 6409。
接下来是用C语言实现这一算法的代码示例:
include <stdio.h>
int main() {
int a, b, p;
printf("请输入两个整数: a b(用空格隔开):");
scanf("%d %d", &a, &b);
p = gcd(a, b); // 调用函数求最大公约数
printf("(%d, %d) = %d, ", a, b, p); // 输出最大公约数
printf("[%d, %d] = %d", a, b, a b / p); // 输出最小公倍数(因为pq=ab,所以q=ab/p)
} // 主函数结束
// 求最大公约数的函数实现:
int gcd(int x, int y) {
int r;
while (r != 0) { // 使用辗转相除法求最大公约数
r = x % y;
x = y;
y = r;
} // while循环结束
return x; // 返回最大公约数
} // 函数结束