C++求最大公約數的四種方法思路，供大家參考，具體內容如下
將最近學的求最大公約數的四種方法總結如下：
第一種：窮舉法之一
解釋：拿其中一個數出來，用一個臨時變量（tem）保存，每次都把那兩個數除以這個臨時變量。如果能除斷，直接返回tem；如果不能除斷，tem- -，直到都能除斷，再返回tem。tem就是它們的最大公約數。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <iostream>using namespace std;int CommFactor1(int m, int n); //函數的聲明int main(){ int a, b; cin >> a >> b; cout << "這兩個數的最大公約數為：" << CommFactor1(a,b)<< endl; return 0;}int CommFactor1(int m,int n){ int tem; for (tem = m;; tem--) { if (m % tem == 0 && n % tem == 0) { break; } } return tem;} |
第二種：窮舉法之二
解釋：求出兩數的所有公因子，再把公因子累乘得到最大公約數。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
#include <iostream>using namespace std;int CommFactor2(int m, int n); //函數的聲明int main(){ int a, b; cin >> a >> b; cout << "這兩個數的最大公約數為：" << CommFactor2(a,b)<< endl; return 0;}int CommFactor2(int m,int n){ int i; int factor = 1; for (i=2;i<=m&&i<<n;i++) { while(m % i == 0 && n % i == 0) //這里不能用if語句，因為可能會有重復的公因子 { factor = factor * i; m = m / i; n = n / i; } } return factor;} |
第三種：輾轉相除法
解釋：將兩個數輾轉相除直到余數為0。（具體思想請問度娘）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
#include <iostream>using namespace std;int CommFactor3(int m, int n); //函數的聲明int main(){ int a, b; cin >> a >> b; cout << "這兩個數的最大公約數為：" << CommFactor2(a,b)<< endl; return 0;}int CommFactor3(int m,int n){ int z = n; while (m % n != 0) { z = m % n; m = n; n = z; } return z;} |
第四種：輾轉相減法
解釋：將兩個數輾轉相減直到兩數相等。（具體思想請問度娘）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>using namespace std;int CommFactor4(int m, int n); //函數的聲明int main(){ int a, b; cin >> a >> b; cout << "這兩個數的最大公約數為：" << CommFactor4(a,b)<< endl; return 0;}int CommFactor4(int m,int n){ while (m != n) { if (m > n) { m = m - n; } else { n = n - m; } } return m;} |
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。
原文鏈接：https://blog.csdn.net/qq_46459874/article/details/108628942
