C語言求最小公倍數和最大公約數三種算法

兩個或多個整數公有的倍數叫做它們的公倍數，其中除0以外最小的一個公倍數就叫做這幾個整數的最小公倍數。整數a，b的最小公倍數記為[a，b]，同樣的，a，b，c的最小公倍數記為[a，b，c]，多個整數的最小公倍數也有同樣的記號。與最小公倍數相對應的概念是最大公約數，a，b的最大公約數記為（a，b）。關於最小公倍數與最大公約數，我們有這樣的定理：(a,b)[a,b]=ab(a,b均為整數)。接下來，為大家介紹一下C語言求最小公倍數和最大公約數三種算法。

方法

求最小公倍數算法：
最小公倍數=兩整數的乘積÷最大公約數
求最大公約數算法：
(1)輾轉相除法
有兩整數a和b：
① a%b得餘數c
② 若c=0，則b即為兩數的最大公約數
③ 若c≠0，則a=b，b=c，再回去執行①
例如求27和15的最大公約數過程為：
27÷15 餘1215÷12餘312÷3餘0因此，3即為最大公約數

⑵ 相減法
有兩整數a和b：
① 若a>b，則a=a-b
② 若a<b，則b=b-a
③ 若a=b，則a（或b）即為兩數的最大公約數
④ 若a≠b，則再回去執行①
例如求27和15的最大公約數過程為：
27－15＝12( 15>12 ) 15－12＝3( 12>3 )
12－3＝9( 9>3 ) 9－3＝6( 6>3 )
6－3＝3( 3==3 )
因此，3即為最大公約數

⑶窮舉法

有兩整數a和b：
① i=1
② 若a，b能同時被i整除，則t＝i
③ i++
④ 若 i <= a(或b)，則再回去執行②
⑤ 若 i > a(或b)，則t即為最大公約數，結束
改進：
① i= a(或b)
② 若a，b能同時被i整除，則i即為最大公約數，
結束
③ i--，再回去執行②
有兩整數a和b：
① i=1
② 若a，b能同時被i整除，則t＝i
③ i++
④ 若 i <= a(或b)，則再回去執行②
⑤ 若 i > a(或b)，則t即為最大公約數，結束
改進：
① i= a(或b)
② 若a，b能同時被i整除，則i即為最大公約數，
結束
③ i--，再回去執行②