Pythonプログラム：数の一意な素因数の積を求める方法

はじめに

本記事では、次の問題に対する解き方を学びます。

問題文： 整数 n が与えられたとき、その数が持つ一意な（重複しない）素因数をすべて求め、それらの積を返します。

例：

入力：num = 11
出力：積は 11
説明：
入力された数は 11 で、素因数は 11 のみです。
したがって、その積も 11 となります。

アプローチ1：総当たり法（ブルートフォース）

i = 2 から n+1 までの for ループを使い、i が n の約数であるかどうかを確認します。約数であれば、さらに i 自身が素数かどうかを判定し、素数なら積に掛け合わせます。この処理を i が n に達するまで繰り返します。

実装例

def productPrimeFactors(n):
    product = 1
    for i in range(2, n + 1):
        if n % i == 0:
            isPrime = 1
            for j in range(2, int(i / 2) + 1):
                if i % j == 0:
                    isPrime = 0
                    break
            if isPrime:
                product = product * i
    return product

# main
n = 18
print(productPrimeFactors(n))

出力

6

18 の場合、一意な素因数は 2 と 3 なので、積は 2 × 3 = 6 となります。この方法はロジックがシンプルで理解しやすい反面、各約数ごとに素数判定を行うため、n が大きくなると計算量が増加し、非効率になるという欠点があります。

アプローチ2：効率的な素因数分解

計算量を抑えるために、以下の手順で素因数分解を行います。

• n が 2 で割り切れる間（偶数の間）、2 を積に掛け、n を 2 で割り続けます。
• ステップ1の後、n は必ず奇数になります。そこで i = 3 から √n までの範囲で for ループを回します。i が n を割り切れる間、i を積に掛けて n を i で割ります。割り切れなくなったら i を 2 ずつ増やして処理を続けます。
• n が 2 より大きい素数である場合、上記の2ステップだけでは n は 1 になりません。そのため、最後に n が 2 より大きければ n 自身を積に掛けます。

実装例

import math

def productPrimeFactors(n):
    product = 1
    # 素因数 2 を処理
    if n % 2 == 0:
        product *= 2
        while n % 2 == 0:
            n = n // 2
    # ここで n は必ず奇数になっている
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        # i が n を割り切る間、i を積に掛けて n を割る
        if n % i == 0:
            product = product * i
            while n % i == 0:
                n = n // i
    # n が 2 より大きい素数の場合
    if n > 2:
        product = product * n
    return product

# main
n = 8
print(int(productPrimeFactors(n)))

出力

2

8 の場合、一意な素因数は 2 のみなので、積は 2 となります。この方法では試し割りの範囲を √n までに限定できるため、計算量は O(√n) 程度に抑えられ、総当たり法と比べて大幅に高速です。

まとめ

本記事では、与えられた整数の一意な素因数の積を求める2つの方法——シンプルな総当たり法と、√n まで試し割りを行う効率的な手法——を紹介しました。小さな数であれば前者でも十分ですが、大きな数を扱う場合は後者の効率的なアプローチを選ぶことをおすすめします。