素因数分解（試し割り法)

試し割り法

試し割り法(ためしわりほう、英: trial division)は最も面倒ではあるが、最も理解しやすい素数判定（素因数分解）アルゴリズムである。基本的な考え方は、素因数分解しようとする整数nを小さい順に割ってみて、割り切れるかどうかを調べる手法である。例えば、12という整数は、1, 2, 3, 4, 6, 12で割り切ることが可能である。

方法

与えられた整数 n (n はこれから素因数分解する整数）に対して、nより小さい数で割り切れるかどうかを順番に確かめることで素数判定を行う。nが2で割り切れる確率は、nが3で割り切れる確率より高いため、小さい数から順に素因数の候補として割り切れるかを確かめると効率的である。また、nが何らかの数pで割り切れる場合、n=pqであり、p<qの時、p<\(\sqrt {n}\)であるから、nの素因数の前半は\(\sqrt {n}\)までで十分ある。前半がわかれば、nをpで限界まで割ることで、同時に後半もわかるため、素数判定を行う判定は\(\sqrt {n}\)までで良い。

筆者の考え方

N=p*q (p<q) の時
p<=√N


Nが素因数を持つ時、"最小の素因数"は、√N以下に必ず存在する
->√N以下の範囲の最小の素因数でNを割れるだけ割って、この値をN(0)とする


N(0)が素因数を持つ時、最小の素因数は、√N(0)以下に必ず存在する
->√N(0)以下の範囲の最小の素因数で割れるだけ割って、更新した値をN(1)とする


N(1)が素因数を持つ時、最小の素因数は、√N(1)以下に必ず存在する
->√N(1)以下の範囲の最小の素因数で割れるだけ割って、更新した値をN(2)とする


...


N(2)が素因数を持つ時、最小の素因数は、√N(2)以下に必ず存在する
->√N(i)以下の範囲の最小の素因数で割れるだけ割って、更新した値をN(2)とする


...


Nは更新するたびに順当に最小の素因数で割られていくので、いずれ√N以下に素因数が存在しなくなる


[√N'以下にもう素因数が存在しない]
->N'は前半(√N'以下)に因数を持たないのでN'=pqでは表せない。
1 か 素数 のどちらかである

試し割り法は、最小の素因数を順当に取り除いていって、√Nを超えた時点で最後の素数判定を行い、全ての素因数を取得する方法。

ポイントは、素因数で割って、Nを更新し、その度に、"最小の素因数は√N以下に存在する"という規則を利用していること。

これを気づくのに丸一日使いました。

しっかり理屈を覚えましょう。

実装

素因数分解

List[int]で素因数を返すやり方

python

def factorize(n):
    b = 2
    fct = []
    # 素因数の前半部分を探す
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1

    # 素因数の後半部分を追加
    if n > 1:
        fct.append(n)
    return fct


n = 2**2 * 3 * 5**3
print(factorize(n))

出力結果

[2, 2, 3, 5, 5, 5]

List[Tuple[int, int]]で素因数を返すやり方

python

def factorize(n):
    fct = []
    b, e = 2, 0  # 素因数, 塁上
    while b * b <= n:
        while n % b == 0:
            n //= b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

n = 2**2 * 3 * 5**3
print(factorize(n))

出力結果

[(2, 2), (3, 1), (5, 3)]

一つ解説すると、 while b * b <= n: の部分はb<=\(\sqrt {n}\)を表し、あえて、平方根を取らないのは、コンピュータによっては意外とsinやcos, ルートの処理は重かったりするからである。