求最大公约数问题（C++）

【题目描述】

给定两个正整数，求它们的最大公约数。

【输入】

输入一行，包含两个正整数(<1,000,000,000)。

【输出】

输出一个正整数，即这两个正整数的最大公约数。

【输入样例】

6 9

【输出样例】

3

这道题方法多，我就列举3个 No.1: 暴力枚举代码：

#include<bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; for(int i=min(a,b);i>=1;i--) { if(a%i==0&&b%i==0) { cout<<i<<endl; return 0; } } return 0; }

结果： No.2: 辗转相除法代码：

#include<bits/stdc++.h> using namespace std; int a,b; int gcd(int a,int b) { int n=max(a,b); int m=min(a,b); if(n%m==0) return m; return gcd(n%m,m); } int main() { cin>>a>>b; cout<<gcd(a,b)<<endl; return 0; }

结果： No.3: 更相减损法代码：

#include<bits/stdc++.h> using namespace std; int a,b; int gcd(int a,int b) { int n=max(a,b); int m=min(a,b); if(n%m==0) return m; return gcd(n-m,m); } int main() { cin>>a>>b; cout<<gcd(a,b)<<endl; return 0; }

结果： 所以最后还是辗转相除法最优。 辗转相除法讲解：

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。 例如：a和b（a>b）的最大公约数是a%b和b的最大公约数

更相减损法讲解：

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。 例如：a和b（a>b）的最大公约数是a-b和b的最大公约数

方法还有很多，但我就列举这三个，我就写到这了，再见。