A. 試し割り法

　試し割り法 (Trial division) は, 素因数分解アルゴリズムの中では最も効率の悪い方法ですが, 簡単に理解することができます. 試し割り法の基本的な考えは, 素因数に分解される整数 $n$ を $n$ より小さい整数で, ただ割っていくことです.

　$n$ の素因数を出力するだけなら,

def junk(n):
    """正の整数を素因数分解して出力する."""
    for i in range(2, n):
        while n % i == 0:
            n //= i
            print(i)
    if n > 1:
        print(n)

最小の素因数 $2$ から繰り返し割っていけば, 割り切れる整数に素数が残っていくことは明らかなので、あとは残った $n$ が $n > 1$ であるならば, それが最後の素因数となります.

　$n$ を素因数分解したとき, $\sqrt{n}$ 以上の素因数は多くても一つしか含まれないので, 最大の因数は $\sqrt{n}$ としていいことがわかります。例えば $n=360$ のとき, 最大の因数は $\sqrt{n}\ \fallingdotseq\ 18.97367$ となります. ここで $\lfloor \sqrt{n} \rfloor = 18$ としてしまうと誤差がでるため, $\lfloor \sqrt{n} \rfloor + 1$ もしくは $\lceil \sqrt{n} \rceil$ とします.

Python による実装 (1)

def trial_division(n):
    """正の整数を素因数分解し, リストで返す."""
    if n == 1:
        return [1]
    factors = []
    for i in range(2, int(n**0.5) + 1 + 1):
        while n % i == 0:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

実行例

trial_division(360)
[2, 2, 2, 3, 3, 5]

計算量

$\pi(2^{n/2})$