谢谢了哈,我后来总算弄明白了,我把它发上来,希望对和我一样的新手有帮助!
用辗转相除法求最大公约数和最小公倍数??我们在程序设计中，经常会遇到一些在一大堆数据中，求这些数据共有特性的情况。下面我们以两个例子向大家介绍这种算法。 ??一般地说，求最小公倍数用两个数的积除以最大公约数即可，而求最大公约数有两种算法： ??1.穷举法，从较小数由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数， ??2.辗转相除法，又名欧几里德算法，是计算最大公约数和最小公倍数的重要方法，比穷举法简便得多。 ??主要过程是(设两数为a，b，a>b)： ??1)a除以b得余数c； ??2)令a=c，b除以a得余数c； ??3)如果a不等于b则跳回1)，否则结束，最后一次的余数就是两数的最大公约数。 ??下面我们用C语言(Turbo C 2.0)来分别演示这两种方法。 ??程序一：??#include ??int max(a,b)｛????if(a>=b)? ??return(a);?? ??else ??return(b);｝??? ??int zdgys(int a,int b)｛? ? ??int m;???for(m=max(a,b);m>0;m--)? ??if((a%m==0)&&(b%m==0))break;???return(m);?} ? ??int zxgbs(int a,int b,int y)? ???｛return(a*b/y;｝??? ??main()?? ???｛int I,j,k,l;???scanf("%d,%d",&I,&j);?? ??k=zdgys(I,j);????l=zxgbs(I,j,k);?? ??printf("%d和%d的最大公约数是：%d，最小公倍数是：%d",I,j,k,l)??? ??程序二：??#include ??int zdgys(int a,int b) ? ?｛ ??int c,d;? ??if(b>a)? ???｛c=a;a=b;b=c;｝?? ??for(;;)｝???? ? ??d=a%b;???if(d==0)? break;? ??a=b;? ??b=d;｝? ? ??return(b);｝?? ? ??int zxgbs(int a,int b,int y)? ???｛return(a*b/y;｝??? ??main()?? ???｛int I,j,k,l;???scanf("%d,%d",&I,&j);?? ??k=zdgys(I,j);???l=zxgbs(I,j,k);?? ??printf("%d和%d的最大公约数是：%d，最小公倍数是：%d",I,j,k,l);｝??
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
例1、用辗转相除法求两个整数的最小公倍数。
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
void main(void)
{
int m,n,r,p;
clrscr();
while(1)
{
gotoxy(10,4);
printf("m,n=? ");
scanf("%d %d",&m,&n);
if (m && n) break;
gotoxy(10,6);
printf(“The datas are invalid, press any key to input again.”);
getch();
gotoxy(10,4);
printf(“%30s”,””);
gotoxy(10,6);
printf(“%50s”,””);
}
p=m*n;
r=m%n;
while(r)
{
m=n;
n=r;
r=m%n;
}
p/=n;
printf("LCM=%d",p);
getch();
}
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
最小公倍数
黄惟明
几个自然数的公倍数中，除0以外，最小的一个叫做这n个自然数的最小公倍数．a1，a2，……，an的最小公倍数记作［al，a2，……，an］．例如， 4和 6的最小公倍数是 12，记作 [4，6]＝12；3，6，9的最小公倍数是18，记作 [3，6，9]＝18．
最小公倍数有下列主要性质：①两个自然数的任意一个公倍数都是它们的最小公倍数的倍数．也就是说：如果［a，b］＝m，而n是a和b的任意一个公倍数，那么m∣n．②两个自然数的最小公倍数与最大公约数的积等于这两个自然数的积．也就是说：〔a，b〕·（a， b）＝ab．
如果两个自然数互质，那么它们的最小公倍数就是这两个数的积．
求几个自然数的最小公倍数，一般有以下两种方法：
①分解质因数法：先把这几个数分别分解质因数，然后把各分解式中出现的所有不同质因数的最高次幂全部连乘起来，所得的积就是它们的最小公倍数．例如，求〔12，30，63〕．
12、30和63这三个数的分解式中的所有不同的质因数是2、3、5、7，出现的2的最高次幂是22，3的最高次暴是32，5和7的最高次幂就是5和7，所以［12， 30， 63］＝22×32×5×7＝1260．
在实际计算中，通常用短除法来计算，把几个数的一切公有的质因数和其中某几个数公有的质因数以及每个独有的质因数的积全部连乘起来，所得的积就是它们的最小公倍数．在上例中，可进行如下：
其中3是三个数公有的质因数，2是两个数公有的质因数，每个数独有的质因数之积是2×5×21
［12， 30， 63］＝3×2×2×5×21＝1260．
②利用最大公约数求最小公倍数：因为〔a，b〕（a，b）＝ab，所以［a，b］＝ab÷（a， b）．也就是说，求两个数的最小公倍数，可以先求出它们的最大公约数，然后用这两个数的积除以它们的最大公约数，所得的商就是这两个数的最小公倍数．
例如，求〔221，143〕．用辗转相除法，可求得（221，143）＝13，所以〔221，143〕＝221×143÷13＝2431．
最小公倍数