辗转相除法的原理不知道你是否能看懂，反正我是看不懂。。。 欧几里得原理(辗转相除法)以及c语言的实现~!2006-07-14 11:26定义一 任给两个整数a,b，其中b≠0, 如果存在一个整数q使得等式 a=bq 成立，则称b整除a,记作b|a 。此时称b为a的约数，a为b的倍数。 定理二 设a,b是两个整数，其中b>0，则存在唯一的整数q及r，使得a=bq+r,0≤rb）的情形给出说明。根据定理二，商q和余r数满足 a=bq+r,且0≤r ≤b-1. 若r=0，显然（a,b）=b;若r≠0,由于a=bq+r，每个能整除b,r的整数都能整除a，当然能同时整除a,b,所以（b,r）|（a,b）;另一方面，r=a-bq，每个能整除a,b的整数都能整除r, 当然能同时整除b,r, 所以(a,b)|(b,r).因此（a,b）=(b,r). 辗转相除法进行一步后，b 取代原来的a，用r取代原来的b,最大公约数保持不变，因此我们的算法可以一直进行下去： a=bq1+r1, b=r1q2+r2, r1=r2q3+r3, … rk-3=rk-2qk-1+rk-1, rk-2=rk-1qk. 一旦出现rk-2=rk-1qk（即rk=0）,则有 rk-1=（rk-2，rk-1）=…=（r1，r2）=（b，r1）=（a，b）. 这个算法用c语言来实现 源代码如下: #include void main() { int a,b,m,n,temp,c,d; printf("请输入两个数字\n"); scanf("%d%d",&m,&n); d=m*n; while (temp) { a=m>n?m:n; b=m<=n?m:n; temp=a%b; m=temp; n=b; } printf("这两个数的最大公约数是%d\n",b); c=d/b; printf("这两个数的最小公倍数是%d\n",c); } (两个数的成积除以两个数的最大公约数就是这两个数的最小公倍数)
