每日一道c语言编程题,第十四题,求两数的最大公约数
用户输入两个数,求这两个数的最大公约数。
#include <stdio.h>
int gcd(int a, int b);
int main() {
int a, b;
printf(\”请输入两个正整数:\\n\”);
scanf(\”%d %d\”, &a, &b);
if (b > a) {
int temp = a;
a = b;
b = temp;
}
printf(\”%d 和 %d 的最大公约数是 %d\\n\”, a, b, gcd(a, b));
return 0;
}
int gcd(int a, int b) {
int temp;
while (b != 0) {
temp = a % b;
a = b;
b = temp;
}
return a;
}
在计算最大公约数时,两个数的大小关系并不影响计算结果。因此,我们可以在程序中对输入的两个数进行大小比较,并将较大的数赋值给 a,较小的数赋值给 b,从而确保 a 是较大的数。
在修改后的代码中,我们使用了一个 if 语句来判断 b 是否大于 a,如果是,则交换 a 和 b 的值。这里我们使用了一个中间变量 temp 来完成交换操作。最后,我们调用 gcd 函数,求解两个数的最大公约数,并输出结果。
需要注意的是,如果输入的两个数相等,则它们的最大公约数就是它们本身,因此在程序中没有对这种情况进行特殊处理。
求两个数的最大公约数及最小公倍数
两个正整数a,b的最大公约数为p,记作:(a,b)=p;最小公倍数为q,记作:[a,b]=q.
例1.求24和30的最大公约数及最小公倍数。
解:对于比较简单的数,可以直接观察出它们的公因数,适合用短除法:
1) 先用24和30的公因数2分别去除两个数24,30,得商12和15;
2) 再用12和15的公因数3分别去除12,15,得商4和5;
3) 4和5已经没有比1大的公因数了,短除法结束。
因为两个公因数2和3 之积为: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时,倒数第二个余数就是这两个数的最大公约数。所以,221和493的最大公约数为:(221,493)=17。
又因为两个数a,b的最大公约数p与最小公倍数q之积pq,等于这两个数之积ab。所以q=(ab)/p.
所以,221余493的最小公倍数为:[221,493]=221*493/17=6409.
用C语言编程如下:
//求两个数a,b的最大公约数p及最小公倍数q
#include <stdio.h>
int main () //注:两个数的最大公约数与最小公倍数之积=这两个数的乘积,即pq=ab,所以q=ab/p
{ int gys(int,int); //函数原型:求最大公约数
int a,b,p;
printf(\”请输入两个整数:a b(两数用空格隔开):\”); scanf(\”%d %d\”,&a,&b);
p=gys(a,b);//调用函数求a,b的最大公约数P
printf(\”(%d,%d)=%d,\”,a,b,p); //输出最大公约数
printf(\”[%d,%d]=%d\”,a,b,a*b/p); //输出最小公倍数(因pq=ab,所以q=ab/p)
}
//求最大公约数函数:
int gys(int x,int y) //函数首部行 ,这里x,y为形式参数
{ int r=1;//使r不为0
while(r!=0) //辗转相除:
{ r=x%y;//求余
x=y;y=r;//辗转
}
return (x); //返回最大公约数x
}
本文作者及来源:Renderbus瑞云渲染农场https://www.renderbus.com
文章为作者独立观点不代本网立场,未经允许不得转载。