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<stdio.h>
void swap(int *,int *);
void main()
{
int a,b,m,n,r;
printf("输入正整数a,b:");
scanf("%d,%d",&a,&b);
if(a<b) swap(&a,&b);
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
责任编辑：cyth
