C语言经典例题100例——C语言练习实例16解答(最大公约数和最小公倍数)

作者(出处):百宝箱工作室发布时间:2017年7月15日 19:47:26查阅量:204

题目:输入两个正整数m和n,求其最大公约数和最小公倍数。

程序分析:

(1)最小公倍数=输入的两个数之积除于它们的最大公约数,关键是求出最大公约数;

(2)求最大公约数用辗转相除法(又名欧几里德算法)。

1)证明:设c是a和b的最大公约数,记为c=gcd(a,b),a>=b,

令r=a mod b

设a=kc,b=jc,则k,j互素,否则c不是最大公约数

据上,r=a-mb=kc-mjc=(k-mj)c

可知r也是c的倍数,且k-mj与j互素,否则与前述k,j互素矛盾。

由此可知,b与r的最大公约数也是c,即gcd(a,b)=gcd(b,a mod b),得证。

2)算法描述:

第一步:a对b求余,令r为所得余数且r!=0,第二步:交换数据,并返回第一步。

程序源代码:

main()
{
    int a,b,t,r,n;
    printf("请输入两个数字:\n");
    scanf("%d %d",&a,&b);
    if(a<b)
    {
		t=b;
		b=a;
		a=t;
	}
    r=a%b;
    n=a*b;
    while(r!=0)
    {
        a=b;
        b=r;
        r=a%b;
    }
    printf("这两个数的最大公约数是%d,最小公倍数是%d\n",b,n/b);
}

以上实例运行结果如下:

请输入两个数字:
30 68
这两个数的最大公约数是2,最小公倍数是1020
百宝箱网络工作室  版权所有  
站长QQ:1617818397  站长E-mail:1617818397@qq.com
Powered by www.baibaox.com  Copyright © 2011-2017
点击这里给我发消息