c語言：
#include<stdio.h>
main()
{
inta,b,c,n,m;
scanf("%d,%d",&n,&m);
if(m<n)
a=m;
m=n;
n=a;
}
c=n*m;
while(n!=0)
b=m%n;
n=b;
printf("公約數%d\n公倍數%d\n",m,c/m);
質因數分解法
質因數分解
質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
例如：求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。
短除法
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然
後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
短除法求最小公倍數，先用這幾個數的公約數去除每個數，再用部分數的公約數去除，並把不能整除的數移下來，一直除到所有的商中每兩個數都是互質的為止，然後把所有的除數和商連乘起來，所得的積就是這幾個數的最小公倍數，例如，求12、15、18的最小公倍數。
短除法的格式
短除法的本質就是質因數分解法，只是將質因數分解用短除符號來進行。
短除符號就是除號倒過來。短除就是在除法中寫除數的地方寫兩個數共有的質因數，然後落下兩個數被公有質因數整除的商，之後再除，以此類推，直到結果互質為止（兩個數互質）。
而在用短除計算多個數時，對其中任意兩個數存在的因數都要算出，其它沒有這個因數的數則原樣落下。直到剩下每兩個都是互質關係。
求最大公因數便乘一邊，求最小公倍數便乘一圈。
無論是短除法，還是分解質因數法，在質因數較大時，都會覺得困難。這時就需要用新的方法。
輾轉相除法
古希臘數學家歐幾里德
輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德演算法。
這就是輾轉相除法的原理。
輾轉相除法的格式
例如，求（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與第二步中等數的乘積就是所求的最大公約數。
其中所說的“等數”，就是最大公約數。求“等數”的辦法是“更相減損”法。所以更相減損法也叫等值演算法。
例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.[1]
比較輾轉相除法與更相減損術的區別
（1）都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。
（2）從結果體現形式來看，輾轉相除法體現結果是以相除餘數為0則得到，而更相減損術則以減數與差相等而得到。
c語言：
#include<stdio.h>
main()
{
inta,b,c,n,m;
scanf("%d,%d",&n,&m);
if(m<n)
{
a=m;
m=n;
n=a;
}
c=n*m;
while(n!=0)
{
b=m%n;
m=n;
n=b;
}
printf("公約數%d\n公倍數%d\n",m,c/m);
}
質因數分解法
質因數分解
質因數分解法：把每個數分別分解質因數，再把各數中的全部公有質因數提取出來連乘，所得的積就是這幾個數的最大公約數。
例如：求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。
短除法
短除法：短除法求最大公約數，先用這幾個數的公約數連續去除，一直除到所有的商互質為止，然
後把所有的除數連乘起來，所得的積就是這幾個數的最大公約數。
短除法求最小公倍數，先用這幾個數的公約數去除每個數，再用部分數的公約數去除，並把不能整除的數移下來，一直除到所有的商中每兩個數都是互質的為止，然後把所有的除數和商連乘起來，所得的積就是這幾個數的最小公倍數，例如，求12、15、18的最小公倍數。
短除法的格式
短除法的本質就是質因數分解法，只是將質因數分解用短除符號來進行。
短除符號就是除號倒過來。短除就是在除法中寫除數的地方寫兩個數共有的質因數，然後落下兩個數被公有質因數整除的商，之後再除，以此類推，直到結果互質為止（兩個數互質）。
而在用短除計算多個數時，對其中任意兩個數存在的因數都要算出，其它沒有這個因數的數則原樣落下。直到剩下每兩個都是互質關係。
求最大公因數便乘一邊，求最小公倍數便乘一圈。
無論是短除法，還是分解質因數法，在質因數較大時，都會覺得困難。這時就需要用新的方法。
輾轉相除法
古希臘數學家歐幾里德
輾轉相除法：輾轉相除法是求兩個自然數的最大公約數的一種方法，也叫歐幾里德演算法。
這就是輾轉相除法的原理。
輾轉相除法的格式
例如，求（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與第二步中等數的乘積就是所求的最大公約數。
其中所說的“等數”，就是最大公約數。求“等數”的辦法是“更相減損”法。所以更相減損法也叫等值演算法。
例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.[1]
比較輾轉相除法與更相減損術的區別
（1）都是求最大公因數的方法，計算上輾轉相除法以除法為主，更相減損術以減法為主，計算次數上輾轉相除法計算次數相對較少，特別當兩個數字大小區別較大時計算次數的區別較明顯。
（2）從結果體現形式來看，輾轉相除法體現結果是以相除餘數為0則得到，而更相減損術則以減數與差相等而得到。