C趣味程序(二)(07)最大公约数与最小公倍数

文章作者 100test 发表时间 2007:03:10 17:39:20
来源 100Test.Com百考试题网

2.1 最大公约数与最小公倍数
试求若干个书籍正整数的最大公约数与最小公倍数。
为方便表述，记：
(a1,a2,...,an)为n个正整数a1,a2,...,an的最大公约数；
{a1,a2,...an}为n个正整数a1,a2,...,an的最小公倍数。

2.1.1 求两个整数a,b(a>b)最大公约数与最小公倍数
算法分析如下：
求两个整数a,b(a>b)的最大公约数通常采用“辗转相除”法；
1)a除以b得余数r；若r=0，则b为所求的最大公约数。
2)若r!=0，以b为a,r为b，继续1)。
注意到任两整数总存在最大公约数，上述辗转相除过程中余数逐步变小，相除过程总会结束。
两整数a,b的最小公倍数与最大公约数有如下简单关系： {a,b}(a,b)=ab
因而由求得的最大公约数即可根据上式求得最小公倍数。
在实际设计中，直接按最大公约数与最小公倍数的定义来实施，显得更为直观，也更为方便。
按“辗转相除法”设计，程序代码如下：
#include
void swap(int *,int *).
void main()
{
int a,b,m,n,r.
printf("输入正整数a,b:").
scanf("%d,%d",&.a,&.b).
if(a m=a.n=b.r=a%b.
while(r!=0)
{
a=b.b=r.
r=a%b.
}
printf("( %d, %d ) = %d\n",m,n,b).
printf("{ %d, %d } = %d\n",m,n,m*n/b).
}
void swap(int *a,int *b)
{
int temp.
temp=*a.
*a=*b.
*b=temp.
}
程序运行结果如下：
输入正整数：a,b 90,108
(108,90) = 18
{108,90} = 540