兩個數(shù)的最大公約數(shù)怎么求？

思考題目的同時，我在這也順便發(fā)出三個靈魂疑問？

• 什么又是更相減損法?
• 什么又是輾轉(zhuǎn)相除法?
• 什么又是歐幾里得算法?

不懂沒關(guān)系，往下看

要解決兩數(shù)的最大公約數(shù)問題？，你首先要知道什么是兩數(shù)的公約數(shù)

解釋：

• 最大公因數(shù)，也稱最大公約數(shù)、最大公因子，指兩個或多個整數(shù)共有約數(shù)中最大的一個。
• 如果數(shù)a能被數(shù)b整除，a就叫做b的倍數(shù)，b就叫做a的約數(shù)。約數(shù)和倍數(shù)都表示一個整數(shù)與另一個整數(shù)的關(guān)系，不能單獨(dú)存在。如只能說16是某數(shù)的倍數(shù)，2是某數(shù)的約數(shù)，而不能孤立地說16是倍數(shù)，2是約數(shù)
• ==例子:== 12、16的公約數(shù)有1、2、4，其中最大的一個是4，4是12與16的最大公約數(shù)，一般記為（12，16）=4。12、15、18的最大公約數(shù)是3，記為（12，15，18）=3。

那如何求呢？

其實(shí)這個問題的解法就在我開頭提的三個疑問中。解決兩數(shù)的最大公約數(shù)問題，可以有很多種方法，而上面提到的二種是最常見的（因?yàn)橛幸环N是重復(fù)的）

畫重點(diǎn)了:
歐幾里得算法分析：

1.歐幾里德算法又稱輾轉(zhuǎn)相除法，簡稱gcd
2, 該算法原理：以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為 0 時，取當(dāng)前算式除數(shù)為最大公約數(shù)
3.該算法證明：請同志們移至度娘

gcd流程圖：

如果gcd算法不好理解，那解決這道問題，可以直接用“枚舉法”（也稱為暴力算法）

枚舉算法分析：

• 求a、b兩個數(shù)的最大公因數(shù)。如果這兩個數(shù)的最大公因數(shù)恰好是a、b其中一個，那肯定是a、b中較小者。==例如：== 2、4的最大公因數(shù)是2
• 那我們可以先求出a、b最小者，然后讓a、b兩數(shù)分別和最小者求余，直到a、b兩數(shù)同時求余結(jié)果為0時就結(jié)束循環(huán)，否則最小值自減一，然后繼續(xù)循環(huán)

上代碼

Java大哥

1

Python新競大哥

1

最后有興趣一起交流的，可以關(guān)注我的公眾號：這里你能夠?qū)W到很實(shí)用的技巧，不是常用的我不說，年底還會抽獎送出我學(xué)過計算機(jī)相關(guān)專業(yè)的書籍福利。敬請期待！！！！

http://weixin.qq.com/r/SUiMlL-EuOLHrfv39x1b (二維碼自動識別)

總結(jié)

以上是生活随笔為你收集整理的一个数里有那些约数用c++怎么做_两数的最大公约数你会求吗？（内附完整算法代码）...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。