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

2023年8月24日
2024年11月4日
プログラミング
Google Colab, Python, 小学校算数

プログラミング

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

こちらの記事では、効率的な最大公約数の求め方として広く知られている「連除法」に焦点を当て、その理解を深めていきます。直感的な手順に従ったPythonによるプログラミングを通して連除法の仕組みを詳しく解説します。さらに、連除法の限界を考えつつ、代替手法として「ユークリッドの互除法」についても紹介します。

最大公約数は、最小公倍数の計算や分数の約分、そして高校で学ぶ等比級数の取り扱いなど、さまざまな数学的な概念で重要な役割を果たします。そのため、しっかりとその概念を理解しておくことが大切です。本記事を通じて、最大公約数に関する理解を深めていきましょう。

1 最大公約数とは
2 連除法とは
3 Pythonでの連除法の実装
4 連除法の問題点
5 ユークリッドの互除法とは
6 まとめ

最大公約数とは

繰り返しになりますが、最大公約数は、2つ以上の整数の共通の約数のうち最も大きいものを意味します。例えば、56の約数は「1, 2, 4, 7, 8, 14, 28, 56」、42の約数は「1, 2, 3, 6, 7, 14, 21, 42」で、56と42の公約数は「1, 2, 7, 14」、最大公約数は「14」です。通常、小学校の算数ではこのようにそれぞれの数の約数を列挙し、共通する約数のなかで最大値を見つけ出すことで最大公約数を求める方法を学習するかと思います。

リンク

下図は、約数の効率的な見つけ方を示したものです。かけたら対象の数（ここでは56又は42）になる組み合わせを上段と下段に書き出していき、枠内に書かれた数が約数になります。

ちなみに最大公約数は、次の特性を持っています。

1を除く全ての整数の最大公約数は必ず1以上です。
2つの整数の最大公約数は、それらの整数を割り切る整数のうち、最も大きなものです。
最大公約数が1である2つの整数を互いに素（相互に約数を持たない）と呼びます。

連除法とは

最大公約数の求め方にはいくつかの方法がありますが、特に「連除法」は、手計算で最大公約数を求める場合において、直感的に理解しやすく、小さな数に対して効果的な方法です。

連除法により最大公約数を求める手順は次のとおりです。ここでは24と36の最大公約数を求めます。

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

Pythonでの連除法の実装

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

対象となる整数をカンマ区切りで入力させる。
与えられた複数の整数の中で、すべての整数を割り切れる共通の数を見つけるために、最も小さい数の約数の素数（素因数）の一覧をリストアップします。
求めた素因数を使って、すべての整数を順番に割り算していきます。
最終的な処理結果を表示します。

特にポイントとなるのは、②で素因数を求める部分です。紙に書きながら手計算する場合には、直感的にすべての整数を割り切れる共通の数を見つけ出すことは比較的容易ですが、コンピュータにとっては困難な作業です。

そこで、与えられた整数のうち最も小さい整数の素因数を見つけて、それですべての整数が割り切れるかどうかを確認していくことにしています。

対象となる整数を入力するブロック

try:
    input_numbers = input("複数の整数をカンマで区切って入力してください：")
    numbers = [int(i) for i in input_numbers.split(',')]
    print()
    # 2未満の数が入力された場合のエラーメッセージを表示
    if any(i < 2 for i in numbers):
        print("error：2より小さい数が含まれています。")  
        return
...

except ValueError:
    print("error：無効な入力です。整数を入力してください。")

▸input関数で対象となる複数の整数をカンマ区切り（「24,36」「24,36,12」など）で入力させます。

▸入力された文字列をsplitメソッドでカンマで分割し、numbersリストに整数で格納します。

▸2未満の整数が入力されている場合はエラーメッセージを表示します。

▸さらに、try-except文による例外処理により整数以外が入力された場合にもエラーを表示します。

素因数のリストアップするブロック

# 入力された数の中で最も小さい数の約数のうち素数（素因数）を配列に格納
primes = list_prime_divisors(min(numbers))

# 素因数を表示
print(f"{min(numbers)}の素因数 = ",end="")
for prime in primes:
    print(prime, end=" ")
print("\n")

▸list_prime_divisors関数で入力された数の中で最も小さい数の約数のうち素数（素因数）をprimesリストに格納します。list_prime_divisors関数の内容は次に示します。

▸求められた素因数の一覧を表示しています。

# 与えられた数の約数のうち素数（素因数）をリストに格納する関数
def list_prime_divisors(num):
    divisors = []
    for i in range(1,num+1):
        if num % i == 0 and is_prime(i):
            divisors.append(i)
    return divisors

▸list_prime_divisors関数は、与えられた数の素因数を求めてリストに格納して返します。

▸求められた素因数を格納するdivisorsリストを宣言します。

▸for文の中でrange関数を使って、 1 から与えられた数までの範囲の数が約数かどうか（割って余りがあるかどうか）を一つずつ確認しています。range関数の下限値は 0 なので 1 を加えています。

例えば「range(10)」では、「0～9（0,1,2,3,4,5,6,7,8,9）」までの範囲が得られます。 また、「range(5,10)」では、「5～9（5,6,7,8,9）」までの範囲が得られます。

▸同様にfor文の中でis_prime関数を使って素数かどうかの確認をしています。is_prime関数の内容は次に示します。

▸確認した数が約数かつ素数（素因数）であればdivisorリストに格納します。

# 与えられた数が素数かどうか判定する関数(試し割り)
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/2までの奇数に対してループを実施
    for i in range(5, int(num/2) + 1,2):
        # 割り切れれは素数ではない
        if num % i == 0:
            return False
    # ループ内で割り切れなければ素数
    return True

▸is_prime関数は、与えられた数が素数かどうかを判定します。もし素数であれば関数は True を返し、素数でなければ False を返します。素数の判定にはいくつかの方法がなアルゴリズムが存在しますが、ここでは「試し割り法」を採用しています。「試し割り法」は、直感的には理解しやすい方法ですが、大きな数に対してはパフォーマンスが低下する可能性があります。

▸最初に特定の数に対して初期処理を行います。与えられた数が 1 であれば素数でないと判断し、 2又は3 であれば素数と判断します。さらに、 2 以外の偶数は素数でないと判断します。

▸次に 5 から与えられた数の 1/2 まで¹（1/2 を超えると明らかに割り切れないので）の奇数に対して割り切れるかどうかを繰り返し、割り切れれば素数でないと判断し、割り切れなければ素数と判断します。

例えば、与えられた数が「23」の場合、「5,7,9,11」の各整数で割ってみます。
　23 ÷  5 = 4... 3（割り切れない）
　23 ÷  7 = 3... 2（割り切れない）
　23 ÷  9 = 2... 5（割り切れない）
　23 ÷ 11 = 2... 1（割り切れない）
どの整数でも割り切れなかったため、「23」は素数です。

素因数で順番に割り算するブロック

gcd=1   # 最大公約数
sp=0    # 先頭スペース調整
pnum=0  # 素因数リストのインデックス

# リストに格納された素因数で順番に処理
while(pnum<len(primes)):
    # リストの各数が当該素因数で割り切れるか判別
    if all(i % primes[pnum] == 0 for i in numbers):
        # リストの各数が当該素因数で割り切れる場合、当該素因数と割られる前のリストの各数を表示
        print(primes[pnum],"|",end=" ")
        for i in numbers:
            print(i," ",end="")
        print("\n-------------------------")

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

        # 最終行作成のため当該素因数の桁数を一時保存
        sp=len(str(primes[pnum]))
        # 最大公約数を当該素因数で更新
        gcd *= primes[pnum]
    else:
        # リストの各数に当該素因数で割り切れない数が含まれている場合、次の素因数に移動
        pnum+=1

▸このブロックで使用する変数（gcd,sp,pnum）を初期化します。

▸while文でprimesリスト内の要素（素因数）の数だけwhile文内の処理を繰り返します。

▸if文でnumbersリスト内の全ての数がprimes[pnum]（現在の素因数）で割り切れるかどうかall関数を用いてチェックします。

▸もし全ての数が割り切れる場合は、素因数とnumbersリストの数を表示し、区切り線を表示します。

▸numbersリスト内の各数を現在の素因数で割って更新します。

▸最終行の作成のために、現在の素因数の桁数（sp）を一時保存し、最大公約数（gcd）を更新します。

▸もし全ての数が割り切れない場合は、次の素因数に移動して処理を続行します。

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

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

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

▸最終的なnumbersリスト内の各数を表示します。また、先頭部分には素因数の桁数（sp）分の空白を含み最終行とします。

▸最後に最大公約数（gcd）を表示します。

プログラムの全文

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

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

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

プログラムを実行すると「複数の整数をカンマで区切って入力してください」とメッセージが表示されますので「24,36」のようにカンマ区切りで入力し実行してください。2つの数だけでなく3つ以上の数にも対応しています。

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

# 与えられた数が素数かどうか判定する関数
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/2までの奇数に対してループを実施
    for i in range(5, int(num/2) + 1,2):
        # 割り切れれは素数ではない
        if num % i == 0:
            return False
    # ループ内で割り切れなければ素数
    return True

# 与えられた数の約数のうち素数（素因数）をリストに格納する関数
def list_prime_divisors(num):
    divisors = []
    for i in range(1,num+1):
        if num % i == 0 and is_prime(i):
            divisors.append(i)
    return divisors

# メイン関数
def main():
    try:
        input_numbers = input("複数の整数をカンマで区切って入力してください：")
        numbers = [int(i) for i in input_numbers.split(',')]
        print()

        # 2未満の数が入力された場合のエラーメッセージを表示
        if any(i < 2 for i in numbers):
            print("error：2より小さい数が含まれています。")
            return

        # 入力された数の中で最も小さい数の約数のうち素数（素因数）をリストに格納
        primes = list_prime_divisors(min(numbers))

        # 素因数を表示
        print(f"{min(numbers)}の素因数 = ",end="")
        for prime in primes:
            print(prime, end=" ")
        print("\n")

        gcd=1   # 最大公約数
        sp=0    # 先頭スペース調整
        pnum=0  # 素因数リストのインデックス

        # リストに格納された素因数で順番に処理
        while(pnum<len(primes)):
            # リストの各数が当該素因数で割り切れるか判別
            if all(i % primes[pnum] == 0 for i in numbers):
                # リストの各数が当該素因数で割り切れる場合、当該素因数と割られる前のリストの各数を表示
                print(primes[pnum],"|",end=" ")
                for i in numbers:
                    print(i," ",end="")
                print("\n-------------------------")

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

                # 最終行作成のため当該素因数の桁数を一時保存
                sp=len(str(primes[pnum]))
                # 最大公約数を当該素因数で更新
                gcd *= primes[pnum]
            else:
                # リストの各数に当該素因数で割り切れない数が含まれている場合、次の素因数に移動
                pnum+=1

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

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

    # 整数以外が入力された場合のエラーメッセージを表示
    except ValueError:
        print("error：無効な入力です。整数を入力してください。")

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

Google Colaboratory への転記

Google Colaboratory での実行結果

連除法の問題点

連除法は、与えられた数列の中から共通の素因数を見つけるために、各数を素因数分解（素数の約数で割って分解）をしています。

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

例えば、504114 と 45877 の最大公約数を求めるとき、直感的に公約数を見つけ出すことは困難です。公約数の 13 を見つけるためには、手計算で 3,5,7,9,11,13 と順番に割っていく必要がありますし、最初の公約数である 13 で割った、38778 と 3529 にさらに公約数があるかどうかの判断も多くの時間がかかります。なお、 504114 と 45877 の最大公約数は 13 です。

また、さらに大きな数になると、素因数分解を含む各ステップで計算量が増加するため、プログラムで処理を行っても多くの時間を要する可能性があります。

このように、大きな数や多数の数列に対しては効率性の問題が生じることがあります。

大きな数に対しても効率的に最大公約数を求める有効な方法として、「ユークリッドの互除法」があげられます。連除法の効率性に制約を感じる場合は、ユークリッドの互除法の利用を検討してください。次に、ユークリッドの互除法の特徴について紹介します。

ユークリッドの互除法とは

ユークリッドの互除法は、2つの整数の最大公約数を効率的に求めるための手法です。

この方法は連除法に比べて計算が簡単なことから、アルゴリズムが理解し易く、プログラムへの実装も比較的容易です。特に、大きな数に対しても迅速に最大公約数を求めることができます。

ユークリッドの互除法では、2つの整数 a と b に対して、 a を b で割った余り（ a % b ）を求め、その余りを b として再度割る、という計算を繰り返します。この計算を余りが 0 になるまで続けると、最終的に b が最大公約数となります。

例として、整数 48 と 18 の最大公約数をユークリッドの互除法で求めます。

まず、 48 を 18 で割ります。
- 48 ÷ 18 = 2 … 12
次に、余り 12 を新しい除数として、 18 を 12 で割ります。
- 18 ÷ 12 = 1 … 6
同様に、余り 6 を新しい除数として、 12 を 6 で割ります。
- 12 ÷ 6 = 2 … 0
余りが 0 になるため、最後に割った除数（ここでは 6 ）が最大公約数となります。

したがって、 48 と 18 の最大公約数は 6 と求められます。

ユークリッドの互除法の証明には、2つの整数 a と b において、GCD(a, b) = GCD(b, r) が成り立つことを示します。ここで GCD は最大公約数を、r は a を b で割った余剰（余り）を表します。
さらに、 GCD(a, b)において、b = 0 であれば、0 の約数は全ての整数なので、GCD(a, 0) = a が成り立ちます。

➀ b ≠ 0 の場合、a を b で割った商を p 、余りを rとすると、a = bp + r と表せます。
⓶ a と b の最大公約数 GCD(a, b) = G と便宜的に置き換えます。
③ a = a'G 、b = b'G と表せます（a'、b'はそれぞれを最大公約数 G で割った商）。
④ a = bq + r から、r = a - bp = a'G - b'qG = G(a'- b'p) と表せます。
⑤ (a'- b'p) は整数なので、③と④から b と r はともに G を最大公約数に持ちます。
⑥ つまり、a と b の最大公約数 G は、b と r の最大公約数に等しいといえます。
⑦ よって、GCD(a, b) = GCD(b, r) が成り立ちます。

この証明を用いて、ユークリッドの互除法を繰り返し適用することで、余りが 0 になる段階での b が最大公約数となります。

Pythonでの連除法の実装

以下は、ユークリッドの互除法のアルゴリズムをPythonでプログラミングした例です。

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# 例として 48 と 18 の最大公約数を求めてみます
result = gcd(48, 18)
print("最大公約数:", result)

まとめ

この記事では、「最大公約数」という重要な数学的概念に焦点を当て、その求め方を紹介しました。最大公約数は、複数の整数が共通して持つ最大の約数であり、数学の様々な分野で重要な役割を果たします。以下に、本記事の主なポイントをまとめます。

1. 最大公約数の概念と意義

最大公約数は、数学的な概念の中でも基本的なものであり、2つ以上の整数が共通して持つ約数のうち、最も大きなものを指します。この概念は、分数の約分や最小公倍数の計算、等比級数の扱いなど、多岐にわたる数学的な応用において不可欠です。

2. 連除法による最大公約数の求め方

連除法は、最大公約数を求める効率的な手法の一つです。具体的な数を用いて、Python プログラムを通じてその直感的な手順を具体的に示しました。連除法は、複数の数を同時に素因数に分解しながら最大公約数を求める方法であり、直感的な理解がしやすい特徴を持っています。

3. ユークリッドの互除法の導入と理解

ユークリッドの互除法は、連除法の限界を克服し、より効率的に最大公約数を求める方法です。ユークリッドの互除法も簡単なプログラム例を紹介しました。この方法は、数学的な性質に基づいており、広範な応用に使われる信頼性の高いアルゴリズムです。

4. 数学的理解の重要性とプログラミングを通じた学習の効果

最大公約数の理解は、数学の基本的な概念としてだけでなく、プログラミングを通じてその計算方法を学ぶことで、より実践的な知識として定着することを期待しています。数学の基礎を固めることで、高度な数学的問題にも自信を持って取り組むことが可能となります。

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

与えられた数が素数かどうかを判定する際に 1/2 まで数に対して割り切れるかどうかの確認をしました。ところが、1/2 まで確認する必要もなく、平方根までの数で割り切れるかどうかを確認すればよいことが知られています。平方根の考え方は中学以降の数学で学習する範囲ですが参考までに紹介します。

自然数 \(n\) が素数でないとき、\(n\) は 1 以外に少なくとも一つ以上の約数を持ちます。
\(n = a × b\) と表したとき、
\(n = \sqrt{n} × \sqrt{n}\) なので
\(aが\sqrt{n}\) 以上のときは、\(bは\sqrt{n}\) 以下であり、
\(bが\sqrt{n}\) 以上であれば、\(aは\sqrt{n}\) 以下となります。
よって、\(a\) か \(b\) のいずれかは必ず \(\sqrt{n}\) 以下であることがわかります。
このことから、\(\sqrt{n}\) 以下までに約数があれば \(n\) は、素数でないといえます。

従って、プログラムは次のように書き換えることが可能です。
（変更前）for i in range(5, int(num/2)+1 ,2):
（変更後）for i in range(5, int(num**0.5)+1 ,2): ↩︎

コメント（2件）

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

2023年9月21日 1:45 PM

[…] […]

返信
【小学校算数】分数の計算（約分と通分）をPythonプログラミングで理解を深めようより:

2023年10月1日 12:13 AM

[…] […]

返信