C趣味程序(二)(07)公約數與最小公倍數

2.1公約數和最小公倍數
試求書上一些正整數的公約數和最小公倍數。
爲了表達方便，記住:
(a1，a2，...，an)是n個正整數a1，a2，...，安；
{a1，a2，...an}是n個正整數a1，a2，...，安。

2.1.1求兩個整數a和b (a >b)的公約數和最小公倍數的算法分析如下:
兩個整數a和b (a >b)的公約數通常用“繙除法”的方法求；
1)a除以B得到餘數R；如果r=0，那麽b是公約數。
2)如果R！=0，B爲a，r爲B，繼續1)。
注意，任意兩個整數之間縂有一個公約數，餘數在上述一輪又一輪的除法過程中逐漸減少，除法過程縂會結束。
兩個整數a，b的最小公倍數與公約數有如下簡單的關系:{a，b}(a，b)=ab
因此，最小公倍數可由公約數按上述公式求得。
在實際設計中，直接根據公約數和最小公倍數的定義來實現，更加直觀方便。
是按照“輾轉反側除法”設計的，程序代碼如下:
# include
void swap(int *，int *)；
void main()
{
int a，b，m，n，r；
printf("輸入正整數a，b:")；
scanf("%d，%d"，&a，& b)；
if(a m = a；n = b；r = a % b；
while(r！= 0)
{
a = b；b = r；
r = a % b；
}
printf("( %d，%d ) = %d\n"，m，n，b)；
printf("{ %d，%d } = %d\n"，m，n，m * n/b)；
}
void swap(int *a，int * b)
{
int temp；
temp = * a；
* a = * b；
* b = temp；
}
程序運行如下:
輸入一個正整數:a，b 90，108
(108，90) = 18
{108，90} = 540

位律師廻複