求約數的簡便方法

㈠ 求最大公約數的簡便方法

求最大公約數的簡便方法如下：

1、輾轉相除法（歐幾里德法）C語言中用升尺如於計算兩個正整數a，b的最大公約數，採用函數嵌套調用形式進行求兩個數的最大公約數。其演算法過程為：

前提：設兩數為a，b設其中a做被除數，b做除數，temp為余數；Steps：大數放a中，吵啟小數放b中；求a/b的余數；若temp=0則b為最大公約數。如果temp！=0則把b的值給a,temp的值給a。

4、Stein演算法

性質：gcd（kx，ky）=k*gcd（x，y）。

對兩個正整數 x>y。

均為偶數gcd（x，y）=2gcd（x/2，y/2）。

均為奇數gcd（x，y）=gcd（（x+y）/2，（x-y）/2）。

X奇y偶gcd（x，y）=gcd（x-y）/2）。

X偶y奇gcd（x，y）=gcd（x/2，y）。

或gcd（x，y）=gcd（y，x/2）。