C++求最大公約數(shù)四種方法解析
更新時間：2020年09月17日 14:06:59 作者：時光zz
這篇文章主要為大家詳細介紹了C++求最大公約數(shù)四種方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
C++求最大公約數(shù)的四種方法思路，供大家參考，具體內(nèi)容如下
將最近學的求最大公約數(shù)的四種方法總結(jié)如下：
第一種：窮舉法之一
解釋：拿其中一個數(shù)出來，用一個臨時變量（tem）保存，每次都把那兩個數(shù)除以這個臨時變量。如果能除斷，直接返回tem；如果不能除斷，tem- -，直到都能除斷，再返回tem。tem就是它們的最大公約數(shù)。
#include <iostream>
using namespace std;
int CommFactor1(int m, int n); //函數(shù)的聲明
int main()
{
int a, b;
cin >> a >> b;
cout << "這兩個數(shù)的最大公約數(shù)為：" << 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;
}
第二種：窮舉法之二
解釋：求出兩數(shù)的所有公因子，再把公因子累乘得到最大公約數(shù)。
#include <iostream>
using namespace std;
int CommFactor2(int m, int n); //函數(shù)的聲明
int main()
{
int a, b;
cin >> a >> b;
cout << "這兩個數(shù)的最大公約數(shù)為：" << 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語句，因為可能會有重復(fù)的公因子
{
factor = factor * i;
m = m / i;
n = n / i;
}
}
return factor;
}
第三種：輾轉(zhuǎn)相除法
解釋：將兩個數(shù)輾轉(zhuǎn)相除直到余數(shù)為0。（具體思想請問度娘）
#include <iostream>
using namespace std;
int CommFactor3(int m, int n); //函數(shù)的聲明
int main()
{
int a, b;
cin >> a >> b;
cout << "這兩個數(shù)的最大公約數(shù)為：" << 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;
}
第四種：輾轉(zhuǎn)相減法
解釋：將兩個數(shù)輾轉(zhuǎn)相減直到兩數(shù)相等。（具體思想請問度娘）
#include <iostream>
using namespace std;
int CommFactor4(int m, int n); //函數(shù)的聲明
int main()
{
int a, b;
cin >> a >> b;
cout << "這兩個數(shù)的最大公約數(shù)為：" << 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;
}
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C++成員函數(shù)如何當作回調(diào)函數(shù)同時傳遞this指針
這篇文章主要介紹了C++成員函數(shù)如何當作回調(diào)函數(shù)同時傳遞this指針，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要介紹了C語言中邏輯運算符與條件運算符的學習教程,條件運算符問號即三目運算符使用起來十分方便,需要的朋友可以參考下2016-04-04
C語言關(guān)于自定義數(shù)據(jù)類型之枚舉和聯(lián)合體詳解
枚舉顧名思義就是把所有的可能性列舉出來，像一個星期分為七天我們就可以使用枚舉，聯(lián)合體是由關(guān)鍵字union和標簽定義的，和枚舉是一樣的定義方式，不一樣的是，一個聯(lián)合體只有一塊內(nèi)存空間，什么意思呢，就相當于只開辟最大的變量的內(nèi)存，其他的變量都在那個變量占據(jù)空間2021-11-11
C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析
這篇文章主要介紹了C++?基本數(shù)據(jù)類型中int、long等整數(shù)類型取值范圍及原理分析，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11
這篇文章主要為大家詳細介紹了C語言中常見的文件操作，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
在Linux下做QT項目時，需要獲取項目的運行路徑，于是用getcwd函數(shù)進行獲取，然后在Windows下進行測試，發(fā)現(xiàn)獲取到的是程序的項目路徑，即代碼文件路徑，然后再Linux QT中測試，獲取到的又是運行路徑，這就很納悶了。經(jīng)過再三測試，終于發(fā)現(xiàn)了原因2022-10-10
這篇文章主要為大家詳細介紹了C語言使用鏈表實現(xiàn)學生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
C++ Leetcode實現(xiàn)從英文中重建數(shù)字
本文主要介紹了當給你一個字符串s，其中包含字母順序打亂的用英文單詞表示的若干數(shù)字（0-9）時，如何通過Leetcode按升序返回原始的數(shù)字。感興趣的童鞋可以來看看2021-11-11
這篇文章主要介紹了C++單例類模板，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-03-03
這篇文章主要為大家介紹了C語言的遞歸函數(shù)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-01-01