1樓：不滅的太陽心
input m,n
dor=m mod n
m=nn=r
loop until r=0
print mend
求兩個自然數的最大公約數有哪些方法？
2樓：匿名使用者
方法如下：
1、質因數分解法
把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
例如：求24和60的最大公約數，先分解質因數，得24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質因數是2、2、3，它們的積是2×2×3=12，所以，（24，60）=12。
2、短除法
短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
例如：求19和152，13和273的最大公因數．因為152÷19＝8，273÷13＝21．（19和13都是質數．）所以19和152的最大公因數是19，13和273的最大公因數是13．
3、輾轉相除法
求幾個數的最大公約數，可以先求出其中任意兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個數為止。最後所得的那個最大公約數，就是所有這些數的最大公約數。
4、更相減損法
更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
5、查詢因數法
先分別找出每個數的所有因數，再從兩個數的因數中找出公有的因數，其中最大的一個就是最大公因數．
例如：求12和30的最大公因數。
12的因數有：1、2、3、4、6、12；
30的因數有：1、2、3、5、6、10、15、30。
12和30的公因數有：1、2、3、6，其中6就是12和30的最大公因數。
3樓：小肥肥
質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然
後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
輾轉相除法：求幾個數的最大公約數，可以先求出其中任意兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個數為止。最後所得的那個最大公約數，就是所有這些數的最大公約數。
4樓：小小小白
1、觀察法
運用能被2、3、5整除的數的特徵進行觀察．
例如，求225和105的最大公因數．因為225、105都能被3和5整除，所以225和105至少含有公因數（3×5）15．因為225÷15＝15，105÷15＝7。15與7互質，所以225和105的最大公因數是15。
2、查詢因數法
先分別找出每個數的所有因數，再從兩個數的因數中找出公有的因數，其中最大的一個就是最大公因數。
例如，求12和30的最大公因數．
12的因數有：1、2、3、4、6、12；
30的因數有：1、2、3、5、6、10、15、30。
12和30的公因數有：1、2、3、6，其中6就是12和30的最大公因數。
3、分解因式法
先分別把兩個數分解質因數，再找出它們全部公有的質因數，然後把這些公有質因數相乘，得到的積就是這兩個數的最大公因數。
例如：求125和300的最大公因數。因為125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公因數是5×5＝25。
4、關係判斷法
當兩個數關係特殊時，可直接判斷兩個數的最大公因數．例如，兩個數互質時，它們的最大公因數就是這兩個數的乘積；兩個數成倍數關係時，它們的最大公因數就是其中較小的那個數。
5、短除法
為了簡便，將兩個數的分解過程用同一個短除法來表示，那麼最大公因數就是所有除數的乘積。
例如：求180和324的最大公因數。
因為：5和9互質，所以180和324的最大公因數是4×9＝36。
6、除法
當兩個數中較小的數是質數時，可採用除法求解。即用較大的數除以較小的數，如果能夠整除，則較小的數是這兩個數的最大公因數。
例如：求19和152，13和273的最大公因數．因為152÷19＝8，273÷13＝21。（19和13都是質數．）所以19和152的最大公因數是19，13和273的最大公因數是13。
7、縮倍法
如果兩個數沒有之間沒有倍數關係，可以把較小的數依次除以2、3、4……直到求得的商是較大數的因數為止，這時的商就是兩個數的最大公因數。
例如：求30和24的最大公因數．24÷4＝6，6是30的因數，所以30和24的最大公因數是6。
5樓：雨說情感
最大公因數，也稱最大公約數、最大公因子，指兩個或多個整數共有約數中最大的一個。求兩個自然數的最大公約數的方法如下：
1、觀察法
運用能被2、3、5整除的數的特徵進行觀察。
例如，求225和105的最大公因數．因為225、105都能被3和5整除，所以225和105至少含有公因數（3×5）15．因為225÷15＝15，105÷15＝7．15與7互質，所以225和105的最大公因數是15。
2、查詢因數法
先分別找出每個數的所有因數，再從兩個數的因數中找出公有的因數，其中最大的一個就是最大公因數。
例如，求12和30的最大公因數。
12的因數有：1、2、3、4、6、12。
30的因數有：1、2、3、5、6、10、15、30。
12和30的公因數有：1、2、3、6，其中6就是12和30的最大公因數。
3、分解因式法
先分別把兩個數分解質因數，再找出它們全部公有的質因數，然後把這些公有質因數相乘，得到的積就是這兩個數的最大公因數。
例如：求125和300的最大公因數．因為125＝5×5×5，300＝2×2×3×5×5，所以125和300的最大公因數是5×5＝25。
4、關係判斷法
當兩個數關係特殊時，可直接判斷兩個數的最大公因數．例如，兩個數互質時，它們的最大公因數就是這兩個數的乘積；兩個數成倍數關係時，它們的最大公因數就是其中較小的那個數。
5、短除法
為了簡便，將兩個數的分解過程用同一個短除法來表示，那麼最大公因數就是所有除數的乘積。
例如：求180和324的最大公因數。
因為：5和9互質，所以180和324的最大公因數是4×9＝36。
6、除法法
當兩個數中較小的數是質數時，可採用除法求解．即用較大的數除以較小的數，如果能夠整除，則較小的數是這兩個數的最大公因數。
例如：求19和152，13和273的最大公因數．因為152÷19＝8，273÷13＝21．（19和13都是質數．）所以19和152的最大公因數是19，13和273的最大公因數是13。
7、縮倍法
如果兩個數沒有之間沒有倍數關係，可以把較小的數依次除以2、3、4……直到求得的商是較大數的因數為止，這時的商就是兩個數的最大公因數．例如：求30和24的最大公因數．24÷4＝6，6是30的因數，所以30和24的最大公因數是6。
8、求差判定法
如果兩個數相差不大，可以用大數減去小數，所得的差與小數的最大公因數就是原來兩個數的最大公因數．例如：求78和60的最大公因數．78－60＝18，18和60的最大公因數是6，所以78和60的最大公因數是6。
如果兩個數相差較大，可以用大數減去小數的若干倍，一直減到差比小數小為止，差和小數的最大公因數就是原來兩數的最大公因數。
例如：求92和16的最大公因數．92－16＝76，76－16＝60，60－16＝44，44－16＝28，28－16＝12，12和16的最大公因數是4，所以92和16的最大公因數就是4。
例：9193和3567，先用9193÷3567，商2餘2059，再用3567÷2059，商1餘1508，2059÷1508，商1餘551,1508÷551，商2餘406，551÷406，商1餘145，406÷145，商2餘116，145÷116，商1餘29，116÷29，商4除盡。所以最大公約數 29。
6樓：匿名使用者
質因數分解法
質因數分解
質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
例如：求24和60的最大公約數，先分解質因數，得24=2×2×2×3，60=2×2×3×5，24與60的全部公有的質因數是2、2、3，它們的積是2×2×3=12，所以，（24、60）=12。
把幾個數先分別分解質因數，再把各數中的全部公有的質因數和獨有的質因數提取出來連乘，所得的積就是這幾個數的最小公倍數。
例如：求6和15的最小公倍數。先分解質因數，得6=2×3，15=3×5，6和15的全部公有的質因數是3，6獨有質因數是2，15獨有的質因數是5，2×3×5=30，30裡面包含6的全部質因數2和3，還包含了15的全部質因數3和5，且30是6和15的公倍數中最小的一個，所以[6，15]=30。
[1]短除法短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然
後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
短除法求最小公倍數，先用這幾個數的公約數去除每個數，再用部分數的公約數去除，並把不能整除的數移下來，一直除到所有的商中每兩個數都是互質的為止，然後把所有的除數和商連乘起來，所得的積就是這幾個數的最小公倍數，例如，求12、15、18的最小公倍數。[1]
短除法的格式
短除法的本質就是質因數分解法，只是將質因數分解用短除符號來進行。
短除符號就是除號倒過來。短除就是在除法中寫除數的地方寫兩個數共有的質因數，然後落下兩個數被公有質因數整除的商，之後再除，以此類推，直到結果互質為止（兩個數互質）。
而在用短除計算多個數時，對其中任意兩個數存在的因數都要算出，其它沒有這個因數的數則原樣落下。直到剩下每兩個都是互質關係。
求最大公因數便乘一邊，求最小公倍數便乘一圈。
無論是短除法，還是分解質因數法，在質因數較大時，都會覺得困難。這時就需要用新的方法。
輾轉相除法
古希臘數學家歐幾里德
輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德演算法。
這就是輾轉相除法的原理。
輾轉相除法的格式
例如，求（319，377）：
∵ 319÷377=0（餘319）
∴（319，377）=（377，319）；
∵ 377÷319=1（餘58）
∴（377，319）=（319，58）；
∵ 319÷58=5（餘29），
∴ （319，58）=（58，29）；
∵ 58÷29=2（餘0），
∴ （58，29）= 29；
∴ （319，377）=29.
可以寫成右邊的格式。
用輾轉相除法求幾個數的最大公約數，可以先求出其中任意兩個數的最大公約數，再求這個最大公約數與第三個數的最大公約數，依次求下去，直到最後一個數為止。最後所得的那個最大公約數，就是所有這些數的最大公約數。[2]
更相減損法
劉徽《九章算術》
更相減損法：也叫更相減損術，是出自《九章算術》的一種求最大公約數的演算法，它原本是為約分而設計的，但它適用於任何需要求最大公約數的場合。
《九章算術》是中國古代的數學專著，其中的「更相減損術」可以用來求兩個數的最大公約數，即「可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。」
翻譯成現代語言如下：
第一步：任意給定兩個正整數；判斷它們是否都是偶數。若是，則用2約簡；若不是則執行第二步。
第二步：以較大的數減較小的數，接著把所得的差與較小的數比較，並以大數減小數。繼續這個操作，直到所得的減數和差相等為止。
則第一步中約掉的若干個2與第二步中等數的乘積就是所求的最大公約數。
其中所說的「等數」，就是最大公約數。求「等數」的辦法是「更相減損」法。所以更相減損法也叫等值演算法。
例1、用更相減損術求98與63的最大公約數。
解：由於63不是偶數，把98和63以大數減小數，並輾轉相減：
98-63=35
63-35=28
35-28=7
28-7=21
21-7=14
14-7=7
所以，98和63的最大公約數等於7。
這個過程可以簡單的寫為：
（98，63）=（35，63）=（35，28）=（7，28）=（7，21）=（7，14）=（7，7）=7.
例2、用更相減損術求260和104的最大公約數。
解：由於260和104均為偶數，首先用2約簡得到130和52，再用2約簡得到65和26。
此時65是奇數而26不是奇數，故把65和26輾轉相減：
65-26=39
39-26=13
26-13=13
所以，260與104的最大公約數等於13乘以第一步中約掉的兩個2，即13*2*2=52。
這個過程可以簡單地寫為：
（260,104）=（65,26）=（39,26）=（13,26）=（13,13）=13.[3]
比較輾轉相除法與更相減損術的區別
（1）都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。
（2）從結果體現形式來看，輾轉相除法體現結果是以相除餘數為0則得到，而更相減損術則以減數與差
兩個自然數相除所得的商是39 餘數是4，被除數 除數 商及餘數的和等於247，除數是多少
除數是x 那麼被除數是39x 4 所以x 39x 4 39 4 247x 5 被除數 除數 商及餘數分別為a,b,39,4a b 39 4 247 a b 204 a 39b 4 40b 4 204 b 5a 199 由題意得 被除數 除數 247 4 39 204 被除數 39 除數 4 所以 3...
每相鄰的兩個自然數相差多少
每相鄰兩個自然數之間相差1。想知道這個問題很容易，首先要知道什麼是自然數。自然數可以是指正整數 1,2,3,4 亦可以是非負整數 0,1,2,3,4 在數論通常用前者，而集合論和電腦科學則多數使用後者。認為自然數不包含零的其中一個理由是因為人們 尤其是小孩 在開始學習數字的時候是由 一 二 三.開始...
6用這數自然陣列成兩個不同的三位數
不是,最大應該是 631 542 我認為應該是631和542乘出來的面積最大.覺得說的很正確啊.要求積最大的話那這兩個數字的百位應該是6和5咯,然後十位的地方呢,就應該選4和3.但是6乘4出來的數字應該大點吧,然後各位也是一樣的,所以我認為是542和631 不知道對不對 631 542 342002...