[C/C++][最大公因數和最小公倍數]

問題：

輸入兩個正整數m和n，求其最大公因數和最小公倍數。

法一：相減

/*
* File Name: LCM_GCD.c
* Author: MH
* Since 2011/03/08
* Toolkit: Dev C++
*/

# include <stdlib.h>
# include <stdio.h>

int main(){

    int m, n, temp_m, temp_n, temp;

    printf("Please input two integers\n");
    scanf("%d%d", &m, &n);

    temp_m = m;
    temp_n = n;

    if(temp_m < temp_n){    // change two integers if temp_m<temp_n

        temp = temp_m;
        temp_m = temp_n;
        temp_n = temp;
        m = temp_m;
        n = temp_n;

    }

    for(i=1; temp_n>0; i++){        // 輾轉相除法求G.C.D.

        temp_m = temp_m - temp_n;   // G.C.D.一定不會被減掉

        if(temp_m<temp_n){
            temp = temp_m;
            temp_m = temp_n;
            temp_n = temp;
        }

    }

    temp = (m/temp_m)*(n/temp_m)*temp_m;    // L.C.M.

    printf("\nThe Greatest Common Divisor(G.C.D.) of the two integers = %d\n", temp_m);
    printf("The Least Common Multiple(L.C.M.) of the two integers = %d\n\n", temp);

    system("Pause");
    return 0;
}

法二：取餘數

/*
* File Name: LCM_GCD.c
* Author: MH
* Since 2011/03/08
* Toolkit: Dev C++
*/

# include <stdlib.h>
# include <stdio.h>

int main(){

    int m, n, temp_m, temp_n, temp;

    printf("Please input two integers\n");
    scanf("%d%d", &m, &n);

    temp_m = m;
    temp_n = n;

    if(temp_m < temp_n){    // change two integers if temp_m<temp_n
        temp = temp_m;
        temp_m = temp_n;
        temp_n = temp;
        m = temp_m;
        n = temp_n;
    }

    while(temp_m % temp_n != 0){    // 以餘數去求G.C.D.
        temp = temp_n;
        temp_n = temp_m % temp_n;
        temp_m = temp;
    }

    temp = (m/temp_n)*(n/temp_n)*temp_n;    // L.C.M.

    printf("\nThe Greatest Common Divisor(G.C.D.) of the two integers = %d\n", temp_n);
    printf("The Least Common Multiple(L.C.M.) of the two integers = %d\n\n", temp);

    system("Pause");
    return 0;
}

其中GCD也可用遞迴方式求得，道理都是一樣意思的

/*
* File Name: GCD.c
* Author: MH
* Since 2011/03/08
* Toolkit: Dev C++
*/

# include <stdlib.h>
# include <stdio.h>

int GCD(int, int);

int main(){

    int m, n, temp_m, temp_n, temp;

    printf("Please input two integers\n");
    scanf("%d%d", &m, &n);

    temp_m = m;
    temp_n = n;

    if(temp_m < temp_n){    // change two integers if temp_m<temp_n

        temp = temp_m;
        temp_m = temp_n;
        temp_n = temp;
        m = temp_m;
        n = temp_n;

    }

    printf("\nThe Greatest Common Divisor(G.C.D.) of the two integers = %d\n", GCD(m, n));

    system("Pause");
    return 0;
}

int GCD(int m, int n){

    int m, n;

    if((m%n)==0)
        return n;
    else
        return GCD(n, m%n);
}