【小学校算数 × プログラミング】Pythonで「最小公倍数」の求め方を理解しよう！

数学を学ぶ上で、最小公倍数という概念は重要な役割を果たします。最小公倍数とは、複数の整数に共通の倍数のうち、最も小さいもののことです。例えば、 6 と 9 の最小公倍数は 18 です。

最小公倍数は、分数の通分や方程式の解法など、さまざまな場面で必要になります。また、最小公倍数は、周期的なパターンの分析にも役立ちます。

例えば、地球が太陽の周りを一周するのに365日かかり、月が地球の周りを一周するのに27日かかるとしたら、地球と月が同じ位置に戻るまでに何日かかるかという問題は、 365 と 27 の最小公倍数を求めることで解くことができます。

このように、最小公倍数は様々な場面で使われる便利な道具です。Pythonでは、標準ライブラリや外部ライブラリを使って簡単に最小公倍数を計算することができますが、その裏にあるアルゴリズムを理解することも大切です。

そこで、この記事では、効率的な最小公約数の求め方として広く知られている「連除法」を中心に、直感的な手順に沿ったPythonのプログラミングを通して最小公倍数を求める仕組みを詳しく解説します。

最小公倍数は、数学や科学のさまざまな分野で幅広く使用されます。そのため、しっかりとその概念を理解しておくことが大切です。本記事を通じて、最小公倍数に関する理解を深めていきましょう。

最小公倍数とは

繰り返しになりますが、最小公倍数とは、複数の整数に共通の倍数のうち、最も小さいもののことです。例えば、 6 と 9 の最小公倍数は 18 です。

これは、次のように 6 と 9 の倍数をそれぞれ列挙して共通する倍数のうち最も小さい数を見つけることでわかります。通常、小学校の算数ではこのように最小公倍数を求める方法を学習するかと思います。

6 の倍数：6 , 12 , 18 , 24 , 30 , …

9 の倍数：9 , 18 , 27 , 36 , 45 , …

一般に、2つ以上の整数 a, b, c, … の最小公倍数（Least Common Multiple）をLCM(a, b, c, …)と表記します。LCM(a, b, c, …)は、主に以下の性質を持ちます。

• LCM(a, b)は、aとbの積よりも小さいか等しいです。
• LCM(a, a) = a です。つまり、同じ数の最小公倍数はその数自身です。
• LCM(1, a) = a です。つまり、1 と他の数の最小公倍数はその他の数自身です。
• LCM(a, b) = (a × b) ÷ GCD(a, b) です。ここで、GCD(a, b)は a と b の最大公約数です。
• LCM(a, b, c) = LCM(LCM(a, b), c) です。つまり、3つ以上の数の最小公倍数は、2つずつの最小公倍数を求めることで計算することができます。

最小公倍数を求める方法にはいくつかありますが、ここでは次の2つの方法について、概要や手順、メリットとデメリットを説明し、Pythonで実装したコード例を紹介します。

• 連除法を利用する方法
• 最大公約数と最小公倍数の関係を利用する方法

連除法を利用する方法

連除法とは

連除法は、最大公約数を求める効率的な方法として以下の記事でも紹介した通り、各整数を素因数分解して必要な素因数を掛け合わせることで求めます。

関連記事

【小学校算数 × プログラミング】Pythonで「最大公約数」の求め方を理解しよう！

最大公約数は、2つ以上の整数の共通の約数のうち最も大きなものを指します。例えば、整数48と36の最大公約数は12です。これは、48と36の共通の約数であり、それ以上の数では割り切れないことを意味しています。 こちらの記事では、効率的[…]

2つの数の場合

24 と 36 の最小公倍数を求める手順は以下のようになります。最大公約数では左側に書いた数のみを掛け合わしますが、最小公倍数では左側と下側（L字）を掛け合わせます。

1. 割り算の筆算を逆さにしたような形の中に対象となる数を並べる（24 と 36 を並べる）。
2. どちらでも割り切れる数を探して左側に書く（24 と 36 のどちらも割れる 2 を書く）。
3. 対象となる数をそれぞれ左側の数で割った答えを下に書く（12 と 18 を書く）。
4. 下に書いた数がどちらでも 1 でしか割り切れなくなるまで手順②と手順③を繰り返す。
5. 左側と下側に書いた数をすべて掛け合わせると最小公倍数が求められる（LCM(24, 36)=72）。

 3つの数の場合

3つ以上の数の最小公倍数を求めるときは、最大公約数とは計算途中の手順が異なります。例えば、 12 と 24 と 32 の最小公倍数を求める手順は以下のようになります。

1. 割り算の筆算を逆さにしたような形の中に対象となる数を並べる（12 と 24 と 32 を並べる）。
2. いずれでも割り切れる数を探して左側に書く（12 と 24 と 32 のどちらも割れる 2 を書く）。
3. 対象となる数をそれぞれ左側の数で割った答えを下に書く（6 と 12 と 16 を書く）。
4. 2つの数だけでも割り切れる数があれば左側に書き、割り切れない数はそのまま下におろす（3行目では3 と 6 が割れる 3 を書き、 8 はそのまま下におろす）。
5. 下に書いた数がどれか2つの数だけでも 1 でしか割り切れなくなるまで手順②～④を繰り返す。
6. 左側と下側に書いた数をすべて掛け合わせると最小公倍数が求められる（LCM(12, 24, 32)=96）。

連除法で3つ以上の数の最大公約数を求めるときは、3つ以上の数を割り切れる数が 1 以外になくなった時点で割り続ける手順を終了しますが、連除法で最小公倍数を求めるときは、どれか2つの数だけでも割り切れる数があれば割り続ける手順を継続します。手順④が最大公約数と最小公倍数の異なる点です。

プログラムの実装

連除法により最小公倍数を求める手順をPythonのプログラムとして実装していきます。プログラムの概要は次の通りです。

1. 複数の整数の入力：最小公倍数を求める複数の整数をカンマ区切りで入力させ、それらをリストに格納します。
2. 共通する素因数の抽出：リストに格納されている2つ以上の数で共通して割り切れる素因数を抽出します。
3. リストの更新：抽出した素因数の最小値でリストの各数を割って更新します。ただし、割り切れない数は元の数のまま更新します。
4. ループ処理：リストの各数がどれか2つだけでも1でしか割り切れなくなるまで、②と③の手順を繰り返します。
5. 最小公倍数の計算：最後にリストに残った各数と、途中で割った素因数を掛け合わせて最小公倍数を求めます。

連除法でポイントとなるのは、②で素因数を求める部分です。紙に書きながら手計算する場合には、割り切れる共通の数を直感的に見つけ出すことは比較的容易ですが、プログラムでは対象となる数を1つずつ検証していく必要があるため、大きな数になると計算量が膨大になる可能性があります。

複数の整数の入力を行う

このパートでは、メイン関数から get_numbers関数を呼び出して、複数の整数の入力と変換及びエラーハンドリングを行います。

get_numbers関数では、入力された複数の整数（カンマ区切り）を取得し、それらの絶対値を数値型のリストに変換します。入力が無効であった場合はエラーメッセージを表示し、None を返します。

# メイン関数
def main():
    #複数の整数の入力を行う  
    numbers = get_numbers()
    if numbers is None:
        return
･･･

# 複数の整数の入力と変換及びエラーハンドリングを行う関数
def get_numbers():
    try:
        input_numbers = input("複数の整数をカンマで区切って入力してください：")
        numbers = [abs(int(i)) for i in input_numbers.split(',')]
        return numbers
    except ValueError:
        print("error：無効な入力です。整数を入力してください。")
        return None

共通する素因数を抽出する

 このパートでは、メイン関数から list_common_factors関数を呼び出し、与えられた数のうち2つ以上で共通する素因数を抽出します。

list_common_factors関数では、与えられたすべての数を1からその数自身までの全ての数が素因数であるかどうかを is_prime関数で確認しています。さらにその中で共通している素因数のみを抽出して新たなリスト（common_factors）に格納して返しています。

# メイン関数
def main():
･･･
        # リストの数のうち2つ以上で共通する素因数のリストを取得
        common_factors = list_common_factors(numbers)
        if not common_factors: 
            # 共通する素因数がない場合、ループを抜ける
            break
･･･

# 与えられた数のうち2つ以上で共通する素因数のリストを返す関数
def list_common_factors(numbers):
    # 全ての数の素因数を保存するリストを初期化
    factors_dict = []
    # 与えられた数の数だけループ
    for num in numbers:
        # 現在の数の素因数をリストにする関数
        for i in range(1,num+1):
            if num % i == 0 and is_prime(i):
                factors_dict.append(i)
    # 共通する素因数を抽出してリストに格納する
    common_factors = []
    for factor in factors_dict:
         if factors_dict.count(factor) >= 2:
            if factor not in common_factors:
                common_factors.append(factor)
    return common_factors

# 与えられた数が素因数かどうか判定する関数
def is_prime(num):
    # 1以下は素数でない
    if num <= 1:
        return False
    # 2と3は素数
    if num <= 3:
        return True
    # 2以外の偶数は素数ではない
    if num % 2 == 0:
        return False
    # 5からnまでの奇数の平方根までの数に対してループを実施
    for i in range(5, int(num**0.5) + 1,2):
        # 割り切れれは素数ではない
        if num % i == 0:
            return False
    # ループ内で割り切れなければ素数
    return True

抽出した素因数の最小値でリストの更新をループする

このパートでは、抽出した素因数の最小値（prime）で現在のリスト（numbers）の各数を割って更新し、リスト（numbers）の各数がどれか2つだけでも1でしか割り切れなくなるまで繰り返す処理を行います。

for i in numbers: ループでは、リスト（numbers）の各数が取得した素因数（prime）で割り切れるかどうかを確認し、割り切れる数が2つ以上ある場合にはその素因数を出力し、2つ以上ない場合にはループを抜けます。

numbers = [int(i / prime) if i % prime == 0 else i for i in numbers] では、リスト（numbers）の各数を取得した素因数（prime）で割り、割り切れない場合はそのままにします。これにより、リスト（numbers）が更新されます。

lcm *= prime で、取得した素因数（prime）で現在の最小公倍数（lcm）を掛けて更新します。

# メイン関数
def main():
･･･
    while True:
･･･
        # 素因数のリストから最小値を取得    
        prime = min(common_factors)

        df=0
        for i in numbers:
            if i % prime == 0:
                df+=1
        if df >= 2:
            print(prime,"|",end=" ")
            for i in numbers:
                print(i," ",end="")
            print("\n-------------------------")

            # リストの各数を当該素因数で割り更新する
            numbers = [int(i / prime) if i % prime == 0 else i for i in numbers]

            # 最終行作成のため当該素因数の桁数を一時保存
            sp=len(str(prime))

            # 最大公約数を当該素因数で更新
            lcm *= prime
        else:
            break
･･･

処理結果を表示するブロック

最後に残ったリスト（numbers）の各数で lcm を更新し、最終的な lcm（最小公倍数）を表示します。

# メイン関数
def main():
･･･
    # 最終行の生成
    print(" "*sp,"|",end=" ")
    for i in numbers:
        print(i," ",end="")
        lcm *= i

    # 最大公約数の表示
    print("\n\n最小公倍数 =",lcm)

プログラム全体

プログラムの全文を掲載します。このプログラムを「Google Colaboratory」にコピペして実行することができます。「Google Colaboratory」については以下の記事もご参照ください。

関連記事

【プログラミングツール】Pythonの開発と実行におすすめのツール比較：Google Colab vs Visual Studio Code

Pythonの開発と実行には様々なツールがありますが、、初心者にとって特におすすめなのが「Google Colab（正式名称「Colaboratory」）」です。 「Google Colab」は、ブラウザ上で動作するクラウドベースの[…]

プログラムを実行すると「複数の整数をカンマで区切って入力してください」とメッセージが表示されますので「45,27,54」のようにカンマ区切りで入力し実行してください。

# --------------------------------------
# 連除法による最小公倍数の探索プログラム
# --------------------------------------

# 与えられた数が素因数かどうか判定する関数
def is_prime(num):
    # 1以下は素数でない
    if num <= 1:
        return False
    # 2と3は素数
    if num <= 3:
        return True
    # 2以外の偶数は素数ではない
    if num % 2 == 0:
        return False

    # 5からnまでの奇数の平方根までの数に対してループを実施
    for i in range(5, int(num**0.5) + 1,2):
        # 割り切れれは素数ではない
        if num % i == 0:
            return False
    # ループ内で割り切れなければ素数
    return True


# 与えられた数のうち2つ以上で共通する素因数のリストを返す関数
def list_common_factors(numbers):
    # 全ての数の素因数を保存するリストを初期化
    factors_dict = []

    # 与えられた数の数だけループ
    for num in numbers:
        # 現在の数の素因数をリストにする関数
        for i in range(1,num+1):
            if num % i == 0 and is_prime(i):
                factors_dict.append(i)

    # 共通する素因数を抽出してリストに格納する
    common_factors = []
    for factor in factors_dict:
         if factors_dict.count(factor) >= 2:
            if factor not in common_factors:
                common_factors.append(factor)

    return common_factors

# 複数の整数の入力と変換及びエラーハンドリングを行う関数
def get_numbers():
    try:
        input_numbers = input("複数の整数をカンマで区切って入力してください：")
        numbers = [abs(int(i)) for i in input_numbers.split(',')]
        return numbers
    except ValueError:
        print("error：無効な入力です。整数を入力してください。")
        return None

# メイン関数
def main():
    #複数の整数の入力を行う  
    numbers = get_numbers()
    if numbers is None:
        return

    lcm=1   # 最小公倍数
    sp=0    # 先頭スペース調整

    # リストの数がどれか2つだけでも1でしか割り切れなくなるまで繰り返し
    while True:
        # リストの数のうち2つ以上で共通する素因数のリストを取得
        common_factors = list_common_factors(numbers)
        if not common_factors: 
            # 共通する素因数がない場合、ループを抜ける
            break
        # 素因数のリストから最小値を取得
        prime = min(common_factors)

        df=0
        for i in numbers:
            if i % prime == 0:
                df+=1
        if df >= 2:
            print(prime,"|",end=" ")
            for i in numbers:
                print(i," ",end="")
            print("\n-------------------------")

            # リストの各数を当該素因数で割り更新する
            numbers = [int(i / prime) if i % prime == 0 else i for i in numbers]

            # 最終行作成のため当該素因数の桁数を一時保存
            sp=len(str(prime))

            # 最大公約数を当該素因数で更新
            lcm *= prime
        else:
            break

    # 最終行の生成
    print(" "*sp,"|",end=" ")
    for i in numbers:
        print(i," ",end="")
        lcm *= i

    # 最大公約数の表示
    print("\n\n最小公倍数 =",lcm)

# プログラムのエントリーポイント。main関数を呼び出してプログラムを実行します。
if __name__ == "__main__":
    main()

Google Colaboratory への転記

Google Colaboratory での実行結果

連除法の問題点

最小公倍数を求める方法として理解しやすく、手計算の際に一般的に使用される連除法ですが、大きな数や要素数の多くなると、直感的に公約数を見つけ出すことが困難になることがあります。そのため、大きな数の計算には適していません。

さらに、数が大きくなると、各ステップでの素因数分解を含む計算量が増加します。これは、プログラムで処理を行う場合でも同様で、多くの時間を要する可能性があります。

したがって、大きな数や多数の数列に対して最小公倍数を求める際には、連除法の効率性に問題が生じることがあります。これらの問題を解決する方法の一つとして、最大公約数と最小公倍数の関係を利用して最小公倍数を求める方法を紹介します。

最大公約数と最小公倍数の関係を利用する方法

最小公倍数は、整数 a と b の積を、 a と b の最大公約数で割った値として求めることができます。この方法は、最大公約数の計算を利用するため、効率的で大きな数でも適用可能です。つまり、2つの数の最小公倍数を求めるためには、まずその2つの数の最大公約数を見つけることが重要となります。

整数aとbの積をその最大公約数で割ると最小公倍数が求められることは次の通り証明できます。

※整数 a と b の最大公約数を GCD(a, b)、最小公倍数を LCM(a, b) とします。 
 
Step1: GCD(a, b) × LCM(a, b) = a × b であることの証明 
 
a と b が互いに素（GCD(a, b) = 1）である場合、LCM(a, b) = a × b です。これは、互いに素な2つの数の最小公倍数はその積であることから明らかです。 
 
一方、 a と b が互いに素でない場合、GCD(a, b) > 1 です。この場合、 a と b はそれぞれ GCD(a, b)で割り切れます。したがって、a = GCD(a, b) × m、b = GCD(a, b) × nと書くことができます（m と n は整数）。この場合、LCM(a, b) = GCD(a, b) × LCM(m, n) = (a × b) / GCD(a, b) です。 
 
したがって、どちらの場合でも GCD(a, b) × LCM(a, b) = a × b が成り立ちます。 
 
Step2: LCM(a, b) = (a × b) / GCD(a, b) であることの証明 
 
Step1から、LCM(a, b) = (a × b) / GCD(a, b) が得られます。これは、整数 a と b の積を a と b の最大公約数で割ると最小公倍数が求められることを示しています。 
 
以上から、整数 a と b の積を a と b の最大公約数で割ると最小公倍数が求められることが証明されます。この性質は、最大公約数と最小公倍数の間の重要な関係を示しています。

大きな数に対しても効率的に最大公約数を求める有効な方法として、「ユークリッドの互除法」があげられます。ユークリッドの互除法で最大公約数を求める方法は次の記事で紹介しています。

関連記事

【小学校算数 × プログラミング】Pythonで「最大公約数」の求め方を理解しよう！

最大公約数は、2つ以上の整数の共通の約数のうち最も大きなものを指します。例えば、整数48と36の最大公約数は12です。これは、48と36の共通の約数であり、それ以上の数では割り切れないことを意味しています。 こちらの記事では、効率的[…]

ユークリッドの互除法を用いて、2つの整数の最大公約数を求め、その最大公約数で2つの整数の積を割ることにより、最小公倍数を求めるプログラムを次に示します。

# ユークリッドの互除法で最大公約数を求める関数
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 例として 48 と 18 の最大公約数及び最小公倍数を求める
a = 48
b = 18
gcd = gcd(a, b)
lcm = int(a * b / gcd)

print("最大公約数:", gcd)
print("最小公倍数:", lcm)

ただし、ユークリッドの互除法は、2つの整数の最大公約数を求める場合においてのみ利用可能です。3つの整数の最小公倍数をユークリッドの互除法を使って求める手順は以下の通りです。

1. 最初に、2つの整数の最大公約数（GCD）を求めます。これはユークリッドの互除法を使用して行います。
2. 次に、最初の2つの整数の最小公倍数（LCM）を求めます。これは、2つの整数の積をその最大公約数で割ることで得られます。
3. 最後に、得られた最小公倍数と3つ目の整数との最小公倍数を同様に求めます。

以上の手順で、3つの整数の最小公倍数が求まります。この方法は、任意の個数の整数に対しても適用可能です。それぞれの整数に対して順番に同じ操作を行っていくだけです。

おわりに

この記事では、「最小公倍数」という重要な数学的概念に焦点を当て、その求め方を紹介しました。最小公倍数は、複数の整数に共通の倍数のうち最も小さいもので、分数の通分や方程式の解法など、さまざまな場面で必要とされます。

記事では、Pythonを用いて最小公倍数を求める方法を2つ紹介しています。1つ目は「連除法」を利用する方法で、これは直感的な手順に沿ったプログラミングを通じて最小公倍数を求める仕組みを紹介しました。しかし、大きな数や要素数が多い場合には計算量が増えるため、効率的ではありません。

2つ目は「最大公約数と最小公倍数の関係を利用する方法」で、これは大きな数でも適用可能で効率的です。具体的には、2つの整数aとbの積をaとbの最大公約数で割った値として最小公倍数を求めます。この方法では、「ユークリッドの互除法」を用いて最大公約数を求めます。

最小公倍数の概念と求め方を通じて、数学とプログラミングの融合の例を紹介しました。プログラムを通じた学習は、抽象的な数学の概念を具体的に理解する助けとなるだけでなく、論理的思考や問題解決能力も向上させてくれます。これからも数学とプログラミングを通じて知識を深め、そのスキルを実生活や今後の学習、キャリア形成に活かしていただければ幸いです。