C++穷举法求两数最大公约数

Question

只要最大公约数，不要最小公倍数急急急急急i！！！！！

Answer 1

求最大公约数的方法，用交换两个个数，互相取余数较简单，不过按你的要求穷举法 只能这么写了
#include <stdio.h>
int Gcd(int a, int b)
{
int i, gcd = 1;

if(a > b)
{
for(i=1; i<=b; i++) //穷举所有小于b的数，在其中找出能被a,b整除的最大的数，即最大公约数
{
if(b%i==0 && a%i==0 && i>gcd)
{
gcd = i;
}
}

return gcd;
}

if(b > a)
{
for(i=1; i<=a; i++)
{
if(b%i==0 && a%i==0 && i>gcd)
{
gcd = i;
}
}

return gcd;
}
}

int main()
{
int gcd;

gcd = Gcd(8, 12);

printf("%d\n", gcd);
return 0;
}

Answer 2

两个数m,n利用穷举求最大公约数，只要遍历2到m即可
int gcd(int m, int n)
{
int i, t = -1;
for(i = 2; i<m; i++) //遍历
if(m%i==0 && n%i==0)t = i; //t记录最大值
return t;
}本回答被网友采纳

Answer 3

支持楼上的