2025-10-11 23:19:27

求最大公约数（最小公倍数）的四种方法

求两个数的最大公约数（最小公倍数）

最大公约数×最小公倍数=两数相乘

最小公倍数=两数相乘/最大公阿约数

1.辗转相除法（欧几里得算法）

依据定理两个整数的最大公约数等于较小数和两数取模的最大公约数

时间复杂度O（log(n)）

#include

#include

using namespace std;

int main()

{

int a, b,ans;

cin >> a >> b;

int x, y;

x = max(a, b);

y = min(a, b);

//x永远放小的数，y永远放大的数

while (true)

{

if (x % y == 0)

{

ans = y; break;

}

else

{

int tem = x % y;

x = y;

y = tem;

}

}

cout << ans << endl;

return 0;

}

2.辗转相减法/更相减损法

时间复杂度O（log（max(a,b)）

#include

#include

using namespace std;

int main()

{

int a, b, ans, x, y;

cin >> a >> b;

x = a; y = b;

while (true)

{

if (a > b)

a = a - b;

else if (a < b)

b = b - a;

else if (a == b)

{

ans = a;

break;

}

}

cout << ans << endl;

return 0;

}

3.暴力遍历

#include

#include

using namespace std;

int main()

{

int a, b, ans;

cin >> a >> b;

for (int i = min(a, b); i > 0; i--)

{

if (a % i == 0 && b % i == 0)

{

ans = i; break;

}

}

cout <

return 0;

}

4。函数递归

#include

#include

using namespace std;

int gcd(int x,int y)

{

while (true)

{

if (x % y == 0)

return y;

else

return gcd(y, x % y);

}

}

int main()

{

int a, b;

cin >> a >> b;

int x = max(a, b);

int y = min(a, b);

int ans = gcd(x, y);

cout <

return 0;

}