打印本文 打印本文  关闭窗口 关闭窗口  
C趣味程序(二)(07)最大公约数与最小公倍数
作者：佚名  文章来源：不详  点击数  更新时间：2008/4/18 13:58:59  文章录入：杜斌  责任编辑：杜斌
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
打印本文 打印本文  关闭窗口 关闭窗口