公因數如何算比較快

25 40 的公因數是:1.5.
34 51 的公因數是:1.
19 23 的公因數是:1.




希望有幫到你^^

Euclidean algorithm...

25 40 的公因數是多少? 1,5
25=5 *5
40=5 *8

34 51的公因數是多少? 1,17
34=2*17
51=3*17


19 23的公因數是多少? 1
19=1 *19
23=1 *23

輾轉相除法最快
25 40 的公因數是1.5
34 51 的公因數是1
19 23 的公因數是1
參考影片https://www.youtube.com/watch?feature=player_embedded&v=LCrDEAZXHHE

如果打一大串文字解說你可能覺得煩瑣, 請觀看圖文並茂的貼圖:
http://www.google.com.tw/imgres?imgurl=http%3A%2F%2F163.27.162.1%2F98HCF%2Fimages%2F20.BMP&imgrefurl=http%3A%2F%2F163.27.162.1%2F98HCF%2Fnews_1_1_1_1.html&h=597&w=847&tbnid=LWiu907rfj6ySM%3A&zoom=1&docid=Ut3ku6Z6vv-v4M&hl=zh-TW&ei=5EwpVJW0OYXe8AX7roHoBg&tbm=isch&ved=0CCUQMygJMAk&iact=rc&uact=3&dur=293&page=1&start=0&ndsp=15
方法是:利用短除法慢慢求得兩數的最大公因數, 而最大公因數的所有因數當然就是兩數的所有公因數

看起來很簡單, 你的問題也解決了, 但你覺不覺得我用"慢慢"這個詞好像有些蹊蹺, 你的感覺沒有錯 ~ ~ 嘻嘻問題來了:455064和8377674的公因數是多少？

你可能覺得@$%&&%%^#$%#, 好聽地說:抱歉, 病態老師才會出這種題目, 我如果真的遇到這種題目了不起放棄就好了, 反正大考頂多考一題

不用擔心, 教你怎麼做輾轉相除法, 雖然處理這麼大的數還是要花不少時間, 但是你有餘力的話, 花一點時間便能讓你多一分勝算:
http://www.google.com.tw/imgres?imgurl=http%3A%2F%2Fpic.pimg.tw%2Fisvincent%2F1319287347-2866740060.png&imgrefurl=http%3A%2F%2Fisvincent.pixnet.net%2Fblog%2Fpost%2F35982541-excel-%25E8%2587%25AA%25E5%258B%2595%25E7%2594%25A2%25E7%2594%259F%25E8%25BC%25BE%25E8%25BD%2589%25E7%259B%25B8%25E9%2599%25A4%25E6%25B3%2595%25E7%259A%2584%25E9%2581%258B%25E7%25AE%2597%25E9%2581%258E%25E7%25A8%258B&h=598&w=284&tbnid=J3qsMmh6O-DZ0M%3A&zoom=1&docid=DCS-qli_qg9BPM&hl=zh-TW&ei=Y04pVLXpGIrV8gWcn4D4Bg&tbm=isch&ved=0CCkQMygNMA0&iact=rc&uact=3&dur=1041&page=1&start=0&ndsp=16
(以下簡稱455064和8377674為A數和B數) 一開始只有A數和B數在那裡並列著, 然後第一步是以較小的數A數x18=8191152(在不超過B數的情況下找最大倍數), 18寫在B數右邊, 8191152寫在B數下面, 畫一條橫線相減寫下186552
接著, 剛剛從左邊過來, 現在從這邊過去:186522x2=373044(在不超過A數的情況下找最大倍數), 2寫在A數左邊, 373044寫在A數下面, 畫一條橫線相減寫下82020
做到其中一排最底下的數變成0為止, 此時另一排最底下的數就是A數和B數的最大公因數, 輾轉相除法你遲早要學到, 原理暫不贅述, 如果想延伸學習, 請見:
http://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95#.E7.AE.97.E6.B3.95.E6.8F.8F.E8.BF.B0

如果你想問三個數的求法, 那就先求其中兩數的最大公因數, 再求此數和第三數的最大公因數就好了, 不用嫌麻煩, 多一個數多一個步驟, 如此而已

2014-09-29 20:55:44 補充：
還有問題請新開一帖

好像是用輾轉相除法就很快吧,
不知道有沒有比輾轉相除法更快的??