［解決！Python］試し割り法で素因数分解をするには：解決！Python

整数を素因数分解するにはさまざまな方法がある。その中でも一番簡単な「試し割り法」と呼ばれる方法でこれを行う手順を紹介する。

[かわさきしんじ，Deep Insider編集部]

連載目次

def prime_factorization(n):
    result = []
    rng = [2] + list(range(3, int(n ** 0.5) + 1, 2))
    for i in rng:
        while n % i == 0:
            n //= i
            result.append(i)
        if n == 1:  # これ以上の素数はない
            break
    if n > 1:  # nは素因数
        result.append(n)
    return result

# 30を素因数分解すると、2 * 3 * 5 = 30
primes = prime_factorization(30)
print(primes)  # [2, 3, 5]

# 60を素因数分解すると、2^2 * 3 * 5 = 60
primes = prime_factorization(60)
print(primes)  # [2, 2, 3, 5]

# 408を素因数分解すると、2^3 * 3 * 17 = 408
primes = prime_factorization(408)
print(primes)  # [2, 2, 2, 3, 17]

# 素因数分解した結果を式で表現する
d = {}

for n in sorted(set(primes)):
    d[n] = primes.count(n)

print(d)  # {2: 3, 3: 1, 17: 1}

terms = []
for k, v in d.items():
    if v == 1:
        tmp = str(k)
    else:
        tmp = f'{k}^{v}'
    terms.append(tmp)
# terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in d.items()]

result = ' * '.join(terms)
print(result)  # 2^3 * 3 * 17

# collections.Counterクラスを使ってもよい
from collections import Counter

primes = prime_factorization(60)
c = Counter(primes)
print(c)  # Counter({2: 2, 3: 1, 5: 1})

terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in c.items()]
result = ' * '.join(terms)
print(result)  # 2^2 * 3 * 5

# 上記の処理を関数にまとめる
def primes_to_expression(primes):
    d = {}
    for n in sorted(set(primes)):
        d[n] = primes.count(n)
    terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in d.items()]
    return ' * '.join(terms)

primes = prime_factorization(60)
result = primes_to_expression(primes)
print(result)  # 2^2 * 3 * 5

def num_to_prime_expression(n):
    primes = prime_factorization(n)
    return primes_to_expression(primes)

result = num_to_prime_expression(300)
print(result)  # 2^2 * 3 * 5^2

試し割り法による素因数分解

　ある整数nを素因数分解するというのは、その数を素数の積として表現することと言える（因数とはある数を割り切れる数。その因数が素数である場合、これを素因数と呼ぶ）。例えば、30という整数は「2×3×5」という3つの素数の積として表現できる。素因数分解を行う簡単なアルゴリズムとしては「試し割り法」がある。これは対象の整数nを2からsqrt(n)の範囲に含まれる素数で（小さい方から）順に割っていくものだ。割り切れたらその素数は因数であり、割り切れなければ因数ではない。

　ここでは、試し割り法を使って60を素因数分解してみよう。

除数	被除数	結果	備考
2	60	30	2で割り切れるので2は素因数
2	30	15	2で割り切れるので2は素因数。これ以上は2で割れないので3で割ってみる
3	15	5	3で割り切れるので3は素因数。これ以上は3で割れないので5で割ってみる
5	5	1	5で割り切れるので5は素因数。そして、これ以上の素因数はない
60を素因数分解する

　上記の表から60を素因数分解すると「2×2×3×5」と表現できる。

　これをPythonのコードにすると次のようになる。

def prime_factorization(n):
    result = []
    rng = [2] + list(range(3, int(n ** 0.5) + 1, 2))
    for i in rng:
        while n % i == 0:
            n //= i
            result.append(i)
        if n == 1:  # これ以上の素数はない
            break
    if n > 1:  # nは素因数
        result.append(n)
    return result

　本来は素数で割っていくのだが、上のコードでは手抜きをして、2と3以上の奇数で割っていくコードになっている（素数を求めるのを省略）。「range(3, int(n ** 0.5) + 1, 2)」というのが3以上でsqrt(n)の範囲に含まれる奇数の範囲となる。

　for文では今述べた範囲の整数で与えられた整数を除算して、その結果から（余りが0かどうかを基に）除数が素因数かどうかを判定している。素因数であれば、結果のリスト（result）にそれを追加して、その商を次の除算の対象として変数nの値を上書きする（上の表で被除数が変化するのに対応）。

　商が1になったら、それ以上の計算は不要なので（全ての素因数を列挙できたので）ループを終了する。また、除数を含むリスト（rng）の要素が尽きてもループは終了する。後者の場合、変数nの値が1ではないこともある。これは変数nの値が素因数であることを示している（例えば、7や17は素数であり、これらを素因数分解しても7や17のままであり、そうした場合は上記のforループは変数resultに素因数が加えられることがないまま終了し、変数nの値は7や17のままとなる）。 そのときには、その値を素因数のリストに追加する。

　このprime_factorization関数を使って、30、60、408を素因数分解する例を以下に示す。

# 30を素因数分解すると、2 * 3 * 5 = 30
primes = prime_factorization(30)
print(primes)  # [2, 3, 5]

# 60を素因数分解すると、2^2 * 3 * 5 = 60
primes = prime_factorization(60)
print(primes)  # [2, 2, 3, 5]

# 408を素因数分解すると、2^3 * 3 * 17 = 408
primes = prime_factorization(408)
print(primes)  # [2, 2, 2, 3, 17]

素因数分解した結果を式で表現する

　せっかくなので、prime_factorization関数で求めた素因数のリストを基にそれを式として表現した文字列に変換してみよう。

　以下はその手順を示したものだ。辞書dに「素因数: 登場回数」という組みが含まれるようにして、その辞書を基に60なら「2^2 * 3 * 5」のような式（文字列）を作成する。

d = {}

for n in sorted(set(primes)):
    d[n] = primes.count(n)

print(d)  # {2: 3, 3: 1, 17: 1}

terms = []
for k, v in d.items():
    if v == 1:
        tmp = str(k)
    else:
        tmp = f'{k}^{v}'
    terms.append(tmp)
# terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in d.items()]

result = ' * '.join(terms)
print(result)  # 2^3 * 3 * 17

　最初のfor文では集合を作成して、素因数のリストから重複を削除し、それを昇順にソートしてから、集合の各要素が素因数のリストに何個含まれているかをカウントし、その結果を辞書dに格納している。

　リストtermsは「2^2 * 3 * 5」のような式を構成する項を格納する。素因数のリストに何かの値が1つしか含まれない場合は「^1」は不要であり、2つ以上含まれる場合は「^2」「^3」などが必要になるので、2つ目のforループではその判断をして各項を作成し、termに追加している。ただし、これはコメントにあるようにリスト内包表記を使うとコンパクトにまとめられる。

　最後にこれを文字列のjoinメソッドを使って結合することで式の表現（文字列）が得られる。

　なお、素因数の出現回数を求める処理はcollectionsモジュールのCounterクラスを使うと簡単に行える。以下に例を示す。

from collections import Counter

primes = prime_factorization(60)
c = Counter(primes)
print(c)  # Counter({2: 2, 3: 1, 5: 1})

terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in c.items()]
result = ' * '.join(terms)
print(result)  # 2^2 * 3 * 5

　上記の処理を関数にまとめると次のようになる（ここではcollections.Counterクラスを使わないコードとしてある）。

def primes_to_expression(primes):
    d = {}
    for n in sorted(set(primes)):
        d[n] = primes.count(n)
    terms = [str(k) if v == 1 else f'{k}^{v}' for k, v in d.items()]
    return ' * '.join(terms)

primes = prime_factorization(60)
result = primes_to_expression(primes)
print(result)  # 2^2 * 3 * 5

　また、2つの関数をまとめて、整数を与えるとそれを素因数分解した式として返す関数は次のようになる。

def num_to_prime_expression(n):
    primes = prime_factorization(n)
    return primes_to_expression(primes)

result = num_to_prime_expression(300)
print(result)  # 2^2 * 3 * 5^2

「解決！Python」

AI・データサイエンスの学びをここから

初心者向け、データ分析・AI・機械学習・Pythonの勉強方法　＠ITのDeep Insiderで学ぼう