输入两个正整数，输出其最大公约数。-蒲公英云

输入两个正整数，输出其最大公约数。

辗转相除法

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数。

# include<stdio.h>
int main()
{ 
    int num1,num2,t=1;
    scanf("%d %d",&num1,&num2);
    while(t)         //辗转相除法
    { 
        t=num1%num2;
        num1=num2;
        num2=t;
     } 
     printf("%d",num1);
     return 0;
}

对于求最大公约数还可以用：更相减损术。但要考虑其num1与num2的大小。

更相减损术

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。
第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。
则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。
其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

# include<stdio.h>
# include<math.h>
int main()
{ 
    int num1,num2,count=0;
    scanf("%d %d",&num1,&num2);
    if((num1%2==0)&&(num2%2==0))
    { 
        num1/=2;
        num2/=2;
        count++;
    }     //减少运算量
    while(num1!=num2)  //更相减损术
    { 
        if(num1>num2)
        { 
            num1-=num2;
        }
        else
        { 
            num2-=num1;
        }
    }
    num1=num1*pow(2,count);
     printf("%d",num1);
     return 0;
}