　　C言語例文集

　最小公倍数を求める

　自然数x、yの最大公約数をgcd(x, y)、最小公倍数をlcm(x, y)と表すと、gcdとlcmには
　gcd(x, y)×lcm(x, y) = xy
という関係があります。この関係を利用して最小公倍数を求めます。
　最大公約数はユーグリッドの互除法で求めることができるので、最小公倍数はlcm(x, y) = xy÷gcd(x, y)で求めます。

＜サンプルプログラム＞

/****************************************************************************/
#include<stdio.h>

int gcd(int x, int y);  // 最大公約数を求める関数
int lcm(int x, int y);  // 最小公倍数を求める関数

int main()
{
    int x, y;
    int lcm_num;
    printf("最小公倍数を求めます。\n");
    printf("自然数を2つ入力してください。\n");
    printf("1つ目の自然数を入力 -> ");
    scanf("%d", &x);
    printf("2つ目の自然数を入力 -> ");
    scanf("%d", &y);

    lcm_num = lcm(x, y);

    printf("%dと%dの最小公倍数は%dです。\n", x, y, lcm_num);
    printf("\n");

    return 0;
}

// 最大公約数を求める関数
int gcd(int x, int y)
{
    int r;

    if(x == 0 || y == 0)  // 引数チェック
    {
        fprintf(stderr, "引数エラーです。\n");
        return 0;
    }

    // ユーグリッドの互除法
    while((r = x % y) != 0) // yで割り切れるまでループ
    {
        x = y;
        y = r;
    }
    return y;
}

// 最大公約数を求める関数
int lcm(int x, int y)
{
    if(x == 0 || y == 0)  // 引数チェック
    {
        fprintf(stderr, "引数エラーです。\n");
        return 0;
    }

    return (x * y / gcd(x, y));
}
/****************************************************************************/

＜実行結果＞

＜Topページ＞