遞迴/迴圈求解最大公因數

3. 33 / 9 = 3 餘6 4. 9 / 6 = 1 餘3 5. 6 / 3 = 2 餘0，除數3 即可為最大公因數 由以上敘述可得遞迴function：(了解原理後，寫出程式就不是問題) ... 伊のspace～芳香精油＊美容保養＊程式設計 跳到主文 生活點滴.... 仔細觀察－－－－“不可能”這個字【IMPOSSIBLE】， 你也許可以看到－“我可能”　【I’M　POSSIBLE】。

部落格全站分類：心情日記 相簿 部落格 留言 名片 ～relax～ 這是一個悠閒放鬆的部落格，請用輕鬆的心情閱讀文章，在忙碌工作之餘療癒自己的身心。

(最近發現我的文章被複製轉貼且沒有註明出處，本部落格的文章皆為原創，若有引用參考也會註明，如有需求請留言告知，謝謝！) Apr25Mon201109:52 遞迴/迴圈求解最大公因數 民國100年經濟部事業招考題目 因數 因數，又稱約數，是對於整數n，除m而"無餘數"的整數。

相對來說，稱n為該因數的倍數。

因數不限正負，可以用「因數|倍數」或「倍數≡0(mod因數)」（參見同餘）來表達。

例如，(6×7=42)7是42的因數，寫作7|42，亦是42≡0(mod7)。

亦稱“因子”。

一整數被另一整數整除，後者即是前者的因數，如1,2,4都為8的因數。

舉例： 18的因數：1,2,3,6,9,18 24的因數：1,2,3,4,6,8,12,24 公因數 在數學中，公約數，亦稱“公因數”。

如果一個數同時是幾個數的約數，稱這個數為它們的“公約數”；公約數中最大的稱為最大公約數(最大公因數)。

舉例： 18跟24的公因數：1,2,3,6 18跟24的最大公因數：6，最大公因數數學表示法：(18,24)=6 互質 兩個正整數只有一個公因數1時，它們的關係叫做互質。

舉例： 4的因數：1,2,4 9的因數：1,3,9 則4和9互質，(4,9)=1。

最大公因數的求法 1.短除法 (24,36,42)=2*3=6 2.標準分解式法 3.輾轉相除法 舉例：x=42,y=75求x,y最大公因數 1.以較大的數(75)為被除數，較小的數(42)為除數，75/42=1餘33 2.前一步驟的除數為被除數，餘數為除數，42/33=1餘9 3.33/9=3餘6 4.9/6=1餘3 5.6/3=2餘0，除數3即可為最大公因數 由以上敘述可得遞迴function：(了解原理後，寫出程式就不是問題) 遞迴的寫法： intgcd(intx,inty){ if(y==0)/*餘0，除數x即為最大公因數*/ returnx; else returngcd(y,x%y);/*前一步驟的除數為被除數，餘數為除數*/ }   #include"stdafx.h" #include #include intgcd(intx,inty); int_tmain(intargc,_TCHAR*argv[]) { intxin=42,yin=75; intx,y; if(xin #include intgcd2(intx,inty); int_tmain(intargc,_TCHAR*argv[]) { intxin=42,yin=75; intx,y; if(xin usingnamespacestd; intgcd(int,int); intmain(){ intm=0; intn=0; cout<>m>>n; cout< usingnamespacestd; intgcd(int,int); intmain(){ intm=0; intn=0; cout<>m>>n; cout<