m和n的最大公约数
int temp, r ,p;
if(n < m)
{
  temp = n;
   n = m;
   m = temp;
}
p =n * m;
while(m != 0)
{
  r = n % m;
  n = m;
  m = r
}
m是最大公约, p/n是最小公倍

#include "stdafx.h"
#include "iostream.h"


int main(int argc, char* argv[])
{
    int m,n;
    cin>>m>>n;
    if(m<=n&&n%m==0)
        cout<<"最大公约数是"<<n<<endl;
    else
    {
    if(n<=m&&m%n==0)
        cout<<"最大公约数是"<<m<<endl;
    else
        cout<<"最大公约数是"<<m*n<<endl;
    }
    return 0;
}
在c++6.0中试一下

用碾转相除法

#include<stdio.h>
void main()
{ int m,n,r,temp,p;
 printf("请输入两个正整数n,m:");
  scanf("%d,%d",&m,&n);
  if(m>n)
  {temp=n;
  n=m;
  m=temp; //把大的整数放在n中，小的整数放在m中
  }
  p=m*n;  //先将n和m的乘积保存在p中，以便求最小公倍数时用
  while(m!=0)
  {
      r=n%m;//求n和m的最大公约数
      n=m;
      m=r;
  }

     
    printf("它们的最大公约数为:%d\n",n);
    printf("它们的最小公倍数为:%d\n",p/n);

   
}

求两个数的最大公约数：
int euc_gcd(int a,int b)
{
  /*if(a%b==0)return b;
   */
  if(b==0)return a;
  return euc_gcd(b,a%b);
}
非递归形式：
int euc_gcd(int a,int b)
{
  int r=a%b;
  while(r>0)
  {
    a=b;
    b=r;
    r=a%b;
  }
  return b;
}

算法：-->（转http://www.burchin.net/article.asp?id=48）

欧几里德算法又称辗转相除法，我们将两个不全为0的非负整数m和n的最大公约数记为gcd(m,n)，代表能够整除（即余数为0）m和n的最大正整数。欧几里得算法基于的方法是重复应用等式gcd(m,n)=gcd(n,m mod n)，直到m mod n等于0。

我们先来证明gcd(m,n)=gcd(n,m mod n)：m可以表示成m=kn+r，则r=m mod n；假设d是m和n的一个公约数，则有d|m和d|n，而r=m-kn，因此d|r，因此d是(n,m mod n)的公约数；假设d 是(n,m mod n)的公约数，则d|n，d|r，但是m=kn+r，因此d也是(a,b)的公约数；因此(a,b)和(b,a mod b)的公约数是一样的，其最大公约数也必然相等，得证。

具体步骤描述如下：

第一步：如果n=0，返回m的值作为结果，同时过程结束；否则，进入第二步。

第二步：用n去除m，将余数赋给r。

第三步：将n的值赋给m，将r的值赋给n，返回第一步。

伪代码描述如下：

Euclid(m,n)

// 使用欧几里得算法计算gcd(m,n)

// 输入：两个不全为0的非负整数m，n

// 输出：m，n的最大公约数

while n≠0 do

    r ← m mod n

    m ← n

    n ← r

[em3]好像还3不错啊,不过好像还有更好理解的额......

贴多一种.
stein算法(移位相减)：
int Stein(int a, int b)
{
    int aa[255] = {0};
    int ba[255] = {0};
    int ca[255] = {0};
    aa[0] = a;
    ba[0] = b;
    ca[0] = 1;
    for (int i = 0; i < 255; i++)
    {
        if (0 == aa[i])
        {
            return ba[i];
        }
        if (0 == ba[i])
        {
            return aa[i];
        }
        if ((0 == (aa[i] & 1)) && (0 == (ba[i] & 1)))
        {// 都是偶数
            aa[i+1] = aa[i] >> 1;
            ba[i+1]    = ba[i] >> 1;
            ca[i+1] = ca[i] << 1;
        }    
        if ((0 == (aa[i] & 1)) && (1 == (ba[i] & 1)))
        {// an是偶数，bn不是
            aa[i+1] = aa[i] >> 1;
            ba[i+1]    = ba[i];
            ca[i+1] = ca[i];
        }
        if ((0 == (ba[i] & 1)) && (1 == (aa[i] & 1)))
        {// bn是偶数，an不是
            ba[i+1] = ba[i] >> 1;
            aa[i+1]    = aa[i];
            ca[i+1] = ca[i];
        }
        if ((1 == (ba[i] & 1)) && (1 == (aa[i] & 1)))
        {// 都不是偶数
            aa[i+1] = abs(ba[i] - aa[i]);
            ba[i+1]    = aa[i] < ba[i] ? aa[i]:ba[i];
            ca[i+1] = ca[i];
        }
    }
}
网上有种说法如下:
[quote]
为了说明Stein算法的正确性，首先必须注意到以下结论： 

gcd(a,a) = a，也就是一个数和他自身的公约数是其自身 
gcd(ka,kb) = k gcd(a,b)，也就是最大公约数运算和倍乘运算可以交换，特殊的，当k=2时，说明两个偶数的最大公约数必然能被2整除 

有了上述规律就可以给出Stein算法如下： 

1.如果A=0，B是最大公约数，算法结束 
2.如果B=0，A是最大公约数，算法结束 
3.设置A1 = A、B1=B和C1 = 1 
4如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(注意，乘2只要把整数左移一位即可，除2只要把整数右移一位即可) 
5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (很显然啦，2不是奇数的约数) 
7.如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 
n++，转4 
[/quote]
其实应该还包括一个前提:gcd(a,b)=gcd(a-b,b)

问题的引出：如何求出两个数x和y的最大公约数？

    最简单的思路，分别求出x和y的约数，再寻找最大公约数。这个方法是从公约数的定义入手，如果x和y比较大，工作量可想而只，能不能偷懒呢？

    不妨设x>y ，首先能想到的特殊情况是x是y的整倍数，即 x=n*y时（n为正整数），x和y最大公约数就是y了。如果x不是y的整倍数呢？肯定是跟 r=x%y 有某种联系。
    我们令a为x和y的最大公约数，再令 x=n*y+r，那么 (x/a)=n*(y/a)+(r/a)。因为(x/a)是整数，(y/a)是整数，所以(r/a)是整数，即r可以被a整除。我们得出一个有用的结论，a是y和r的公约数。
    下面我们的问题是a是否是y和r的最大公约数，或者和最大公约数有某种联系？
    我们设y和r的最大公约数是b，则有a<=b，还是利用 x=n*y+r，有 (x/b)=n*(y/b)+(r/b)，因为(y/b)是整数，(r/b)是整数，所以(x/b)是整数，即x可以被b整除。得出结论：b是x和y的公约数。因为a是x和y的最大公约数，所以又有 b<=a，结合前面的 a<=b，得出 a=b。即x和y的最大公约数是y和r的最大公约数。

    回到前面的问题，我们已经找出x和y的最大公约数和r之间的某种联系，能否利用他求最大公约数呢？
    我们看看 x y r 三者的大小， 因为 x%y=r，所以y>r ，又因为x=n*y+r ，所以x>r。我们令f(x,y)表示x和y的最大公约数。
    那么有，设  r1=max{x,y}；r2=min{x,y}
               f(r1,r2)=f(r2,r3)   其中r3=r1%r2
               f(r2,r3)=f(r3,r4)   其中r4=r2%r3
               ......
               f( r[i],r[i+1] )=f( r[i+1],r[i+2] )   其中r[i+2]=r[i]%r[i+1]
    这样就可以将f内的两个数缩小下去，直到r[i]是r[i+1]的整倍数，那么r[i+1]即为x和y的最大公约数。

首先列出的是我采用了递归的算法。

//函数原型 int gcd(int x,int y);
//函数功能 求正整数x和正整数y的最大公约数 greatest common divisor
//参数要求 x>0,y>0
//返回值  >0时为x和y的最大公约数，=-1时为参数错误

#define ERROR -1   //参数错误时的返回值

int gcd(int x,int y)
{
      if( x<=0 || y<=0 ) return ERROR;
 
      int temp;
 
      if(x<y)
      {
            temp=x;x=y;y=temp;
      }

      if(x%y==0)
            return y;
      else
            return gcd(y,x%y);
}

接着就是非递归的算法

//函数原型 int gcd(int x,int y);
//函数功能 求正整数x和正整数y的最大公约数 greatest common divisor
//参数要求 x>0,y>0
//返回值   >0时为x和y的最大公约数，=-1时为参数错误

#define ERROR -1    //参数错误时的返回值

int gcd(int x,int y)
{
      if( x<=0 || y<=0 ) return ERROR;
 
      int r;
 
      if(x<y)
      {
            r=x;x=y;y=r;
      }

      while( 0!=(r=x%y) )
      {
            x=y;
            y=r;
      }
 
      return y;
}

想着想着就这样出来的。。。。
   
#include "stdio.h"
main()
{   int m,n,i;
    scanf("%d %d",&m,&n);
    while(m>n)
      { i=(m-n);
       if(i==n)
        printf("%d",n);
       if(i>n)
        m=i;
       else
       {m=n;
        n=i;
       }
      }
    while(n>m)
      { i=(n-m);
       if(i==m)
        printf("%d",m);
       if(i>m)
        n=i;
       else
       { n=m;
         m=i;
       }
      }
    getch();
}