求解输入两正整数的最大公约数，小白请求教

Question

#include
#include

using namespace std;

int main()

{

int x;

int y;

int z=0;
int i = 0;
cin >> x >> y;
    while (x % 2 == 0 && y % 2 == 0)
    {
        x = x / 2;
        y = y / 2;
        i++;
    }
    while (x % 2 == 0 && y % 2 != 0)
    {
        x = x / 2;
    }
    while (x % 2 != 0 && x % 2 == 0)
    {
        y = y / 2;
    }
    while (z != x || z != y)
    {
        z = abs(x - y);
    }
cout << z * pow(2, i);
return 0;

}

Answer 1

你的思路是好的，但是有问题，z=(x-y)之后要对x、y重新赋值，否则一个循环下来什么都没变只能是死循环。
最大公约数一般都用辗转相除法，你先单独提一个2其实没必要，就像如果你事先知道一些素数就可以都单独提一遍。
辗转相除法用的是求余，和相减类似，终止条件是其中一个个被模除或减到0，就是相减复杂点，如下，也可以写成递归。

while(x||y){
    z = abs(x-y);//直接写x-y就行，一般要保证x>=y
    if(z > y)
        x = z;//10-3=7,7-3=4,4-3=1这种情况
    else {
        x = y;//4-3=1要变成3-1的形式，继续下次循环。
        y = z;
    }
}
//模除法
while(x||y){
    z = x % y;
    //下面就简单多了
    x = y;
    y = z;
}