C语言求两个正整数的最小公倍数和最大公约数
1.main()
2.{
3.int p,r,n,m,temp;
4.printf("Please enter 2 numbers n,m:");
5.scanf("%d,%d",&n,&m);//输入两个正整数.
6.if(n<m)//把大数放在n中,把小数放在m中.
7.{temp=n;
8.n=m;
9.m=temp;
10.}
11.p=n*m;//P是原来两个数n,m的乘积.
12.while(m!=0)//求两个数n,m的最大公约数.
13.{
14.r=n%m;
15.n=m;
16.m=r;
17.}
19.printf("Its MAXGongYueShu:%d\n",n);//打印最大公约数.
20.printf("Its MINGongBeiShu:%d\n",p/n);打印最小公倍数
_________________________________________________________________
Q1.分析一下以上程序的12行到17行求最大公约数的算法原理.
Q2.两个正整数的最小公倍数=两个数的最大公倍数÷两个数的最大公约数?
Q3.发散一下,如果推广到3个乃至n个正整数求最小公倍数或者最大公约数该怎么思考一个高效率的算法?
Q4.能否提供一下权威的数学课本上求两个正整数最小公倍数和最大公约数的方法?
注:先设每个问题7.5分,共计30分,如果全部回答且比较好的再奖励20分!
热心的网友们快来抢分吧!
参考答案:Q1、
用欧几里德算法（辗转相除法）求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
例如求1515和600的最大公约数，
第一次：用600除1515，商2余315；
第二次：用315除600，商1余285；
第三次：用285除315，商1余30；
第四次：用30除285，商9余15；
第五次：用15除30，商2余0。
1515和600的最大公约数是15。
Q2、
错误，两个数的最大公倍数是无穷大
应当是两个正整数的最小公倍数=两个数的乘积÷两个数的最大公约数
由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。这就是说，求两个数的最小公倍数，可以先求出两个数的最大公约数，再用这两个数的最大公约数去除这两个数的积，所得的商就是两个数的最小公倍数。
例 求105和42的最小公倍数。
因为105和42的最大公约数是21，
105和42的积是4410，4410÷21＝210，
所以，105和42的最小公倍数是210。
Q3、
原理：
三个数的最小公倍数，取公有的质因数时，除了取三个数公有的质因数外，还要取出其中两个数公有的质因数作除数，而把另一个数移下来。三个数公有的质因数只要取一个，两个数公有的质因数也只要取一个。这样才能保证所取的全部质因数的乘积是三个数的最小公倍数。
算法：
对于3个数A，B，C，最小公倍数=A*B*C/最小公约数的平方
对于对小公约数，可以采用两次辗转相除法
先求A，B的最小公约数D
再求出C与D的最小公约数E
那么E就是这三个数的最小公约数
A*B*C/E/E就是三个数的最小公倍数
Q4、
本答案绝大部分选自九年义务教育教材（修订）六年制教材 教师教学用书 第十册 人民教育出版社
地址：
若有问题请自行翻阅