欧几里德算法（求两个正整数的最大公约数）（转）

C语言版：

/*欧几里德算法：辗转求余
  原理: gcd(a,b)=gcd(b,a mod b)
  当b为0时,两数的最大公约数即为a

  getchar()会接受前一个scanf的回车符
*/

#include

void main()
{
    int temp;
    int a,b;
    scanf("%d",&a);
    scanf("%d",&b);
    printf("the greatest common factor of %d and %d is ",a,b);
    while(b!=0)
    {
        temp=b;
        b=a%b;
        a=temp;
    }
    printf("%d\n",a);
    getchar();
    getchar();
}

C++/java语言版：

    void swap(int & a, int & b)
    {
        int c = a;
        a = b;
        b = c;
    }
    int gcd(int a,int b)
    {
        if(0 == a )
        {
            return b;
        }
        if( 0 == b)
        {
            return a;
        }
        if(a > b)
        {
            swap(a,b);
        }
        int c;
        for(c = a % b ; c > 0  ; c = a % b)
        {
            a = b;
            b = c;
        }
        return b;
    }