今天大概学了下哈希排序，又学了辗转相除法，求最小公倍数和最大公约数都非常方便
以下是网上找的资料：
设两个数m,n，假设m>=n，用m除以n，求得余数q。若q为0，则m为最大公约数；若q不等于0，则进行如下迭代：
m=n,n=q,即原除数变为新的被除数，原余数变为新的除数重复算法，直到余数为0为止。余数为0时的除数n，即为原始m、n的最大公约数。
迭代初值：m，n的原始值；
迭代过程：q=m%n;
m=n;
n=q;
迭代条件：q!=0
例如：m=8;n=6
q=m%n(8%6==2)
m=n(m==6)
n=q(n==2)
因为：(q==2)!=0，重复算法：
q=m%n(6%2==0)
m=n(m==2)余数为0时的除数n为最大公约数，n值赋给了m，所以输出m的值
n=q(n==0)
因为：q==0 所以最大公约数为m的值
源程序：
#include
void main()
{
int m,n,q,a,b;
printf("Enter two integers:");
scanf("%d%d",&a,&b);
m=a;
n=b;
if(n>m)
{
int z;
z=m;m=n;n=z;//执行算法前保证m的值比n的值大
}
do
{
q=m%n;
m=n;
n=q;
}while(q!=0);
printf("The greatest common divisor of");
printf("%d,%d is %dn",a,b,m);
}
