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

2.1 公約數(shù)與最小公倍數(shù)
     試求若干個書籍正整數(shù)的公約數(shù)與最小公倍數(shù)。
     為方便表述，記：
     (a1,a2,...,an)為n個正整數(shù)a1,a2,...,an的公約數(shù)；
     {a1,a2,...an}為n個正整數(shù)a1,a2,...,an的最小公倍數(shù)。
    2.1.1 求兩個整數(shù)a,b(a>b)公約數(shù)與最小公倍數(shù)
    算法分析如下：
     求兩個整數(shù)a,b(a>b)的公約數(shù)通常采用“輾轉(zhuǎn)相除”法；
     1)a除以b得余數(shù)r；若r=0，則b為所求的公約數(shù)。
     2)若r!=0，以b為a,r為b，繼續(xù)1)。
     注意到任兩整數(shù)總存在公約數(shù)，上述輾轉(zhuǎn)相除過程中余數(shù)逐步變小，相除過程總會結(jié)束。
     兩整數(shù)a,b的最小公倍數(shù)與公約數(shù)有如下簡單關(guān)系： {a,b}(a,b)=ab
     因而由求得的公約數(shù)即可根據(jù)上式求得最小公倍數(shù)。
     在實際設(shè)計中，直接按公約數(shù)與最小公倍數(shù)的定義來實施，顯得更為直觀，也更為方便。
    按“輾轉(zhuǎn)相除法”設(shè)計，程序代碼如下：
    #include
    void swap(int *,int *);
    void main()
    {
     int a,b,m,n,r;
     printf("輸入正整數(shù)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;
    }
    程序運行結(jié)果如下：
    輸入正整數(shù)：a,b 90,108
    (108,90) = 18
    {108,90} = 540