【Python】関数を使わずに最小公倍数を求める方法

2024-02-132024-07-21

最小公倍数とは何か、その計算方法や応用例、そして具体的なPythonコードの実装方法まで、わかりやすく説明します。

これを読めば、最小公倍数の基本から実際のプログラムの書き方までしっかり理解できるようになります。

目次から探す

最小公倍数(LCM)とは

最小公倍数(LCM: Least Common Multiple)は、2つ以上の整数の中で、共通の倍数のうち最小のものを指します。

例えば、6と8の最小公倍数は24です。

これは、6と8の両方で割り切れる最小の整数だからです。

最小公倍数の定義

最小公倍数は、2つ以上の整数の共通の倍数の中で最も小さいものです。

具体的には、整数aとbの最小公倍数をLCM(a, b)と表し、次のように定義されます。

LCM(a, b)は、aとbの両方で割り切れる最小の正の整数です。

例えば、a = 6, b = 8の場合、6の倍数は6, 12, 18, 24, 30, …であり、8の倍数は8, 16, 24, 32, …です。

これらの共通の倍数の中で最小のものは24です。

したがって、LCM(6, 8) = 24となります。

最小公倍数の計算方法

最小公倍数を求める方法はいくつかありますが、一般的な方法として以下の2つが挙げられます。

素因数分解を使った方法:

各整数を素因数分解し、それぞれの素因数の最大の指数を持つものを掛け合わせることで最小公倍数を求めます。

例: 12と15の最小公倍数を求める場合

12 = 2^2 * 3
15 = 3 * 5
最小公倍数 = 2^2 * 3 * 5 = 60

最大公約数(GCD)を使った方法:

最大公約数を使って最小公倍数を求める方法もあります。

2つの整数aとbの最小公倍数は、次の式で求められます。

GCDは最大公約数のこと

例: 12と15の最小公倍数を求める場合

12と15の最大公約数(GCD)は3
LCM(12, 15) = (12 * 15) / 3 = 60

最小公倍数の応用例

最小公倍数は、日常生活やさまざまな分野で応用されています。

以下にいくつかの例を挙げます。

時間の計算:

例えば、2つの異なる周期で繰り返されるイベントがある場合、そのイベントが同時に発生する最小の時間を求めるのに最小公倍数が使われます。

例えば、3日ごとに発生するイベントと4日ごとに発生するイベントがある場合、両方のイベントが同時に発生するのは12日後です。

分数の通分:

分数の足し算や引き算を行う際に、分母を揃えるために最小公倍数が使われます。

例えば、1/3と1/4を足す場合、分母の最小公倍数は12なので、1/3 = 4/12, 1/4 = 3/12と変換して計算します。

工業製品の生産計画:

異なる部品の生産サイクルを調整する際に、最小公倍数を使って効率的な生産スケジュールを立てることができます。

例えば、部品Aが5日ごとに生産され、部品Bが7日ごとに生産される場合、両方の部品が同時に生産されるのは35日ごとです。

最小公倍数は、数学的な問題解決だけでなく、実生活やビジネスの場面でも非常に役立つ概念です。

Pythonを使ってこれを計算する方法については、次のセクションで詳しく説明します。

最小公倍数を求めるアルゴリズム

最小公倍数を求めるためにはいくつかの方法があります。

ここでは、素因数分解を使った方法、最大公約数(GCD)を使った方法、そして反復法を使った方法について詳しく解説します。

最小公倍数の基本的な求め方

素因数分解を使った方法

素因数分解を使った方法は、各数を素因数に分解し、それらの素因数の最大の指数を持つものを掛け合わせることで最小公倍数を求める方法です。

具体的には以下の手順で行います。

各数を素因数に分解する。
各素因数の最大の指数を求める。
それらの素因数を最大の指数で掛け合わせる。

例えば、12と18の最小公倍数を求める場合を考えます。

12の素因数分解: 2^2 * 3^1
18の素因数分解: 2^1 * 3^2

この場合、2の最大指数は2、3の最大指数は2です。

したがって、最小公倍数は 2^2 * 3^2 = 4 * 9 = 36 となります。

最大公約数(GCD)を使った方法

最大公約数を使った方法は、2つの数の最大公約数を求め、それを使って最小公倍数を計算する方法です。

具体的には以下の式を使います。

例えば、12と18の最小公倍数を求める場合を考えます。

12と18の最大公約数(GCD)は6です。

したがって、最小公倍数は

となります。

反復法を使った最小公倍数の求め方

反復法の基本概念

反復法は、2つの数の倍数を順に比較していき、最初に一致する倍数を見つける方法です。

この方法はシンプルで理解しやすいですが、効率が悪い場合があります。

反復法の具体的な手順

反復法を使って最小公倍数を求める手順は以下の通りです。

2つの数のうち大きい方の数を初期値とする。
その数が両方の数で割り切れるかを確認する。
割り切れない場合、その数に大きい方の数を加える。
割り切れるまで2と3を繰り返す。

例えば、12と18の最小公倍数を反復法で求める場合を考えます。

初期値は18(12と18のうち大きい方)。
18は12で割り切れないので、18に18を加えて36にする。
36は12でも18でも割り切れるので、最小公倍数は36となる。

このようにして、反復法を使って最小公倍数を求めることができます。

次のセクションでは、Pythonでの具体的な実装方法について解説します。

Pythonでの実装方法

反復法を使った最小公倍数の求め方

初期値の設定

反復法を使って最小公倍数を求めるためには、まず初期値を設定する必要があります。

最小公倍数を求める2つの数値を a と b とします。

初期値として、a と b のうち大きい方の数値を設定します。

これは、最小公倍数が必ず a または b のどちらか以上であるためです。

a = 12
b = 15
# 初期値の設定
lcm = max(a, b)

ループの設定

次に、最小公倍数を見つけるためのループを設定します。

ループは、lcm が a と b の両方で割り切れるまで続けます。

割り切れない場合は、lcm を1ずつ増やして再度チェックします。

while True:
    if lcm % a == 0 and lcm % b == 0:
        break
    lcm += 1

条件分岐の設定

ループ内で条件分岐を設定します。

lcm が a と b の両方で割り切れる場合、ループを終了します。

割り切れない場合は、lcm を1ずつ増やして再度チェックします。

while True:
    if lcm % a == 0 and lcm % b == 0:
        break
    lcm += 1

実装例

具体的なコード例

以下に、反復法を使って最小公倍数を求める具体的なコード例を示します。

# 2つの数値を設定
a = 12
b = 15
# 初期値の設定
lcm = max(a, b)
# 反復法による最小公倍数の計算
while True:
    if lcm % a == 0 and lcm % b == 0:
        break
    lcm += 1
# 結果の表示
print(f"{a} と {b} の最小公倍数は {lcm} です。")