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

この記事では、Pythonを使って関数を使わずに最小公倍数を求める方法を紹介します。

素因数分解やユークリッドの互除法、ループを使った方法など、様々なアプローチを通じて最小公倍数の求め方を学ぶことができます。

目次から探す

最小公倍数の求め方

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

素因数分解を利用して最小公倍数を求める方法は、与えられた2つの数の素因数分解を行い、それぞれの素因数の最大の指数を取り、それらを掛け合わせることで最小公倍数を求めます。

以下にサンプルコードを示します。

def prime_factors(n):
    factors = {}
    i = 2
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors[i] = factors.get(i, 0) + 1
    if n > 1:
        factors[n] = factors.get(n, 0) + 1
    return factors

def lcm(a, b):
    factors_a = prime_factors(a)
    factors_b = prime_factors(b)
    lcm_factors = {}
    
    for factor, count in factors_a.items():
        lcm_factors[factor] = max(lcm_factors.get(factor, 0), count)
    
    for factor, count in factors_b.items():
        lcm_factors[factor] = max(lcm_factors.get(factor, 0), count)
    
    result = 1
    for factor, count in lcm_factors.items():
        result *= factor ** count
    
    return result

# 使用例
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(f"最小公倍数: {result}") # 最小公倍数: 36

方法2: ユークリッドの互除法を使った方法

ユークリッドの互除法を利用して最小公倍数を求める方法は、与えられた2つの数の最大公約数を求め、それを使って最小公倍数を計算します。

以下にサンプルコードを示します。

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

def lcm(a, b):
    return abs(a * b) // gcd(a, b)

# 使用例
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(f"最小公倍数: {result}") # 最小公倍数: 36

方法3: ループを使った方法

ループを使った方法では、与えられた2つの数のうち大きい方の数から始めて、その数の倍数を順番にチェックしていき、最初に共通の倍数を見つけた時点でそれが最小公倍数となります。

以下にサンプルコードを示します。

def lcm(a, b):
    max_num = max(a, b)
    while True:
        if max_num % a == 0 and max_num % b == 0:
            return max_num
        max_num += 1

# 使用例
num1 = 12
num2 = 18
result = lcm(num1, num2)
print(f"最小公倍数: {result}") # 最小公倍数: 36

このように、異なる方法を使ってPythonで関数を使わずに最小公倍数を求めることができます。

目次から探す