【C言語】最小公倍数を求める方法

この記事では、C言語を使って最小公倍数を求める方法について解説します。

目次から探す

方法1: ユークリッドの互除法を使った最小公倍数の求め方

最小公倍数を求める方法の一つに、ユークリッドの互除法を使う方法があります。

ユークリッドの互除法は、2つの数の最大公約数を求めるためのアルゴリズムですが、最小公倍数を求める際にも利用することができます。

ユークリッドの互除法を使って最小公倍数を求める手順は以下の通りです。

  1. 2つの数を入力する。
  2. 入力された2つの数の最大公約数を求める。
  3. 最大公約数を使って最小公倍数を求める。

以下に、C言語でユークリッドの互除法を使って最小公倍数を求めるサンプルコードを示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int num1, num2;
    printf("2つの数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = lcm(num1, num2);
    printf("最小公倍数は %d です。\n", result);
    return 0;
}

上記のコードでは、gcd関数を使って最大公約数を求め、lcm関数を使って最小公倍数を求めています。

main関数では、ユーザーに2つの数を入力してもらい、最小公倍数を計算して表示しています。

ユークリッドの互除法は、2つの数の最大公約数を求めるためのアルゴリズムですが、最小公倍数を求める際にも利用することができます。

方法2: 最小公倍数の性質を利用した最小公倍数の求め方

最小公倍数を求める方法のもう一つの方法は、最小公倍数の性質を利用する方法です。

最小公倍数の性質として、2つの数の積を最大公約数で割ることで最小公倍数を求めることができます。

以下に、C言語で最小公倍数の性質を利用して最小公倍数を求めるサンプルコードを示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    return (a * b) / gcd(a, b);
}
int main() {
    int num1, num2;
    printf("2つの数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = (num1 * num2) / gcd(num1, num2);
    printf("最小公倍数は %d です。\n", result);
    return 0;
}

上記のコードでは、gcd関数を使って最大公約数を求め、最小公倍数の性質を利用して最小公倍数を計算しています。

main関数では、ユーザーに2つの数を入力してもらい、最小公倍数を計算して表示しています。

最小公倍数の性質を利用する方法は、2つの数の積を最大公約数で割ることで最小公倍数を求めることができます。

方法3: 最大公約数を利用した最小公倍数の求め方

最小公倍数を求める方法の最後の方法は、最大公約数を利用する方法です。

最大公約数を求めた後、最小公倍数は2つの数の積を最大公約数で割ることで求めることができます。

以下に、C言語で最大公約数を利用して最小公倍数を求めるサンプルコードを示します。

#include <stdio.h>
// 最大公約数を求める関数
int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}
// 最小公倍数を求める関数
int lcm(int a, int b) {
    int max = (a > b) ? a : b;
    while (1) {
        if (max % a == 0 && max % b == 0) {
            return max;
        }
        max++;
    }
}
int main() {
    int num1, num2;
    printf("2つの数を入力してください: ");
    scanf("%d %d", &num1, &num2);
    int result = lcm(num1, num2);
    printf("最小公倍数は %d です。\n", result);
    return 0;
}

上記のコードでは、gcd関数を使って最大公約数を求め、lcm関数を使って最小公倍数を計算しています。

main関数では、ユーザーに2つの数を入力してもらい、最小公倍数を計算して表示しています。

目次から探す