def prime_factorize(n: int) -> "List[int]":
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    if a == []: # 入力が1のときの例外
        a.append(1)
    return a
print(prime_factorize(12)) # [2, 2, 3]

ret = []
def factor_all_patterns(n: int, start: int, a: "List[int]"):
    while start * start <= n:
        if n % start == 0:
            ret.append(a + [start, n//start])
            factor_all_patterns(n//start, start, a + [start])
        start += 1

factor_all_patterns(n=12, start=2, a=[])
print(ret) # [[2, 6], [2, 2, 3], [3, 4]]