輸入兩個正整數m和n,求其最大公約數和最小公倍數. <1>用輾轉相除法求最大公約數 演算法描述: m對n求餘為a,若a不等於0 則m<-n,n<-a,繼續求餘 否則n為最大公約數 <2>最小公倍數=兩個數的積/最大公約數 #include intmain() { intm,n; intm_cup,n_cup,res;/*被除數,除數,餘數*/ printf("Entertwointeger:\n"); scanf("%d%d",&m,&n); if(m>0&&n>0) { m_cup=m; n_cup=n; res=m_cup%n_cup; while(res!=0) { m_cup=n_cup; n_cup=res; res=m_cup%n_cup; } printf("Greatestcommondivisor:%d\n",n_cup); printf("Leasecommonmultiple:%d\n",m*n/n_cup); } elseprintf("Error!\n"); return0; } ★關於輾轉相除法,搜了一下,在中國古代的《九章算術》中就有記載，現摘錄如下: 約分術曰：“可半者半之，不可半者，副置分母、子之數，以少減多，更相減損，求其等也。以等數約之。” 其中所說的“等數”，就是最大公約數。求“等數”的辦法是“更相減損”法，實際上就是輾轉相除法。 輾轉相除法求最大公約數，是一種比較好的方法，比較快。 對於52317和75569兩個數，你能迅速地求出它們的最大公約數嗎？一般來說你會找一找公共的使因子，這題可麻煩了，不好找，質因子大。 現在教你用輾轉相除法來求最大公約數。 先用較大的75569除以52317，得商1，餘數23252，再以52317除以23252，得商2，餘數是5813，再用23252做被除數，5813做除數，正好除盡得商數4。這樣5813就是75569和52317的最大公約數。你要是用分解使因數的辦法，肯定找不到。 那麼，這輾轉相除法為什麼能得到最大公約數呢？下面我就給大夥談談。 比如說有要求a、b兩個整數的最大公約數，a＞b，那麼我們先用a除以b，得到商8，餘數r1：a÷b＝q1…r1我們當然也可以把上面這個式子改寫成乘法式：a＝bq1＋r1------l） 如果r1＝0，那麼b就是a、b的最大公約數3。要是r1≠0，就繼續除，用b除以r1，我們也可以有和上面一樣的式子： b＝r1q2＋r2-------2） 如果餘數r2＝0，那麼r1就是所求的最大公約數3。為什麼呢？因為如果2）式變成了b＝r1q2，那麼b1r1的公約數就一定是a1b的公約數。這是因為一個數能同時除盡b和r1，那麼由l）式，就一定能整除a，從而也是a1b的公約數。 反過來，如果一個數d，能同時整除a1b，那麼由1）式，也一定能整除r1，從而也有d是b1r1的公約數。 這樣，a和b的公約數與b和r1的公約數完全一樣，那麼這兩對的最大公約數也一定相同。那b1r1的最大公約數，在r1＝0時，不就是r1嗎？所以a和b的最大公約數也是r1了。 有人會說，那r2不等於0怎麼辦？那當然是繼續往下做，用r1除以r2，……直到餘數為零為止。 在這種方法裡，先做除數的，後一步就成了被除數，這就是輾轉相除法名字的來歷吧。

在visual C++ 6.0上，用C語言編寫求最大公因數和最小公倍數的程式。

1開啟visual C++ 6.0-檔案-新建-檔案-C++ Source File。

2輸入預處理命令和主函式：#include<stdio.h> /*函式頭：輸入輸出標頭檔案*/void main() /*空型別：主函式*/。

3定義變數、輸入數值：int a,b,t,c,d,i,f,r; /*定義變數的資料型別為整型*/printf("輸入兩個數，中間用逗號隔開:"); /*輸出文字提示*/scanf("%d,%d",&a,&b); /*輸入兩個數字*/。

4if(a<b) /*用if函式比較a、b大小*/ {t=a; /*如果b大於a，則將a,b數值交換*/ a=b; b=t; }c=a;d=b; /*因為下面的程式會改變a,b的數值，所以將未改變的數值賦 給c,d*/。

5計算最大公因數和最小公倍數：while(r!=0) /*用while函式實現輾轉相除法*/ {r=a%b; /*當餘數為0，停止執行while函式時*/ a=b; /*最大公因數b的值賦給a*/ b=r; } i=c*d; /*將c乘d的值賦給i*/ f=i/a; /*將i除最大公因數a,得到最小公倍數，並將它賦給f*/。

6輸出最大公因數和最小公倍數：printf("最大公因數%d\n",a); /*輸出最大公因數*/ printf("最小公倍數%d\n",f); /*輸出最小公倍數*/。

7完整的原始碼：#include<stdio.h> /*函式頭：輸入輸出標頭檔案*/void main() /*空型別：主函式*/{ /*函式體*/ int a,b,t,c,d,i,f,r; /*定義變數的資料型別為整型*/ printf("輸入兩個數，中間用逗號隔開:"); /*輸出文字提示*/ scanf("%d,%d",&a,&b); /*輸入兩個數字*/ if(a<b) /*用if函式比較a、b大小*/ {t=a; /*如果b大於a，則將a,b數值交換*/ a=b; b=t; } c=a;d=b; /*因為下面的程式會改變a,b的數值，所以將未改變的數值賦給c,d*/ while(r!=0) /*用while函式實現輾轉相除法*/ {r=a%b; /*當餘數為0，停止執行while函式時*/ a=b; /*最大公因數b的值賦給a*/ b=r; } i=c*d; /*將c乘d的值賦給i*/ f=i/a; /*將i除最大公因數a,得到最小公倍數，並將它賦給f*/ printf("最大公因數%d\n",a); /*輸出最大公因數*/ printf("最小公倍數%d\n",f); /*輸出最小公倍數*/}。