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的最大公约数及最小公倍数。

解答:对于不易直接观察出公因数的数字,我们可以使用辗转相除法:

  1. 用较大的数493除以较小的数221,得到商2,余数为51;
  2. 然后,将上面的除数221作为新的被除数,余数51作为新的除数再次相除,得到商4,余数为17;
  3. 再次以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; // 返回最大公约数

} // 函数结束