小道具：素因数分解

素因数分解して結果を出力します。

simple.py

#!/usr/bin/env python3

# 整数の平方根
def lsqrt1(x: int) -> tuple:
    if x < 0:
        raise ArithmeticError
    l, r, s = x.bit_length() >> 1, 0, 0
    for b in range(l, -1, -1):
        r <<= 1
        t = 1 << b
        u = s + t
        v = u << b
        if x < v:
            continue
        x -= v
        r |= 1
        s = u + t
    return (r, x)


# 整数の平方根(Python 3.8 以上)
def lsqrt2(x: int) -> tuple:
    a = isqrt(x)
    return (a, x - a * a)


try:
    from math import isqrt
    lsqrt = lsqrt2
except:
    lsqrt = lsqrt1


# 素因数分解
def factor(N: int) -> tuple:
    f = []

    # 負は正にする
    if N < 0:
        f.append(-1)
        N = -N

    # 2^n で割って奇数にする
    while (N & 1) == 0:
        f.append(2)
        N >>= 1

    # 奇数の素因数分解
    def odd(N: int, ds: int) -> list:
        # 7 以下の場合は素数
        if N <= 7:
            return [N] if N != 1 else []

        # 平方数と除数の上限
        q, r = lsqrt(N)
        if r == 0:
            return odd(q, ds) * 2

        # 奇数の試し割
        for d in range(ds, q + 2, 2):
            q, r = divmod(N, d)
            if r != 0:
                continue

            # 指数を調べる
            e = 1
            while True:
                t, r = divmod(q, d)
                if r != 0:
                    break
                q = t
                e += 1
            return [d] * e + odd(q, d + 2)

        # 素数
        return [N]

    f += odd(N, 3)
    if not f:
        f.append(1)

    # ((素数,指数), ...) の形式に整える
    return tuple([(d, f.count(d)) for d in sorted(set(f))])


# 素因数分解（検算あり）
def factor_debug(N: int) -> tuple:
    f = factor(N)
    c = 1
    for t in [p ** e for p, e in f]:
        c *= t
    if N != c:
        raise Exception(f'Bug:{N} != {c}, {f}')
    return f


def main():
    import argparse
    parser = argparse.ArgumentParser()
    parser.add_argument('N', type=int)
    args = parser.parse_args()
    print(args.N, '=', ' * '.join(e != 1 and f'{p}^{e}' or f'{p}'
                                  for p, e in factor_debug(args.N)))


if __name__ == '__main__':
    main()

実行結果

$ python3 simple.py 1234567890
1234567890 = 2 * 3^2 * 5 * 3607 * 3803

頭の体操

説明が面倒臭い方法で素因数分解します。できるというだけで、アルゴリズム的にはとんでもなく遅いです。

sample.py

#!/usr/bin/env python3

# 素因数分解
def factor(N: int) -> tuple:
    r = []

    if N < 0:
        r.append(-1)
        N = -N

    # 2^n で割って奇数にする
    while (N & 1) == 0:
        r.append(2)
        N >>= 1

    r += factor_odd(N)
    if not r:
        r.append(1)

    # ((素数,指数), ...) の形式に整える
    return tuple([(d, r.count(d)) for d in sorted(set(r))])


# 奇数の素因数分解
def factor_odd(N: int) -> list:
    if N <= 7:
        # 7 以下で 1 以外は素数
        if N == 1:
            return []
        return [N]
    q, r = lsqrt(N)
    if r == 0:
        t = factor_odd(q)
        return t + t
    if (N & 2) == 0:
        return factor_odd_4n1(N, q)
    else:
        return factor_odd_4n3(N, q)


# N = (4n + 1) の場合
def factor_odd_4n1(N: int, q: int) -> list:
    z = N >> 2            # = (N - 1) >> 2
    xmin = (q + 1) >> 1   # = ((q - 1) >> 1) + 1
    xmax = N >> 2         # : (N >> 2) - 1

    for o in range(3):
        for x in range(xmin + o, xmax, 4):
            t = x * x + x - z
            if (t & 2) != 0:  # y^2 = (2k + 1)^2 = 4(k^2 + k) + 1
                continue
            y, r = lsqrt(t)
            if r == 0:
                a = (x + y) * 2 + 1
                b = (x - y) * 2 + 1
                return factor_odd(a) + factor_odd(b)

    # x = 4k + 3
    # x^2 + x = 4(4k^2 + 7k + 3)
    if (z & 2) == 0:
        for x in range(xmin + 3, xmax, 4):
            t = x * x + x - z
            y, r = lsqrt(t)
            if r == 0:               # a = 2x + 1, b = 2y
                m = (x + y) * 2 + 1  # a + b = (2x + 1) + (2y)
                n = (x - y) * 2 + 1  # a - b = (2x + 1) - (2y)
                return factor_odd(m) + factor_odd(n)

    return [N]


# N = (4n + 3) の場合
def factor_odd_4n3(N: int, q: int) -> list:
    z = (N + 1) >> 2
    xmin = (q >> 1) + 1  # = (q >> 1) + 1
    xmax = z             # = (N - 1) >> 2
    for x in range(xmin, xmax):
        t = x * x - z
        s, r = lsqrt(t * 4 + 1)
        if r == 0:
            y = (s - 1) >> 1     # a = 2x, b = 2y + 1
            m = (x + y) * 2 + 1  # a + b = (2x) + (2y + 1)
            n = (x - y) * 2 - 1  # a - b = (2x) - (2y + 1)
            return factor_odd(m) + factor_odd(n)
    return [N]


# 整数の平方根
def lsqrt(x: int) -> tuple:
    if x < 0:
        raise ArithmeticError
    l, r, s = x.bit_length() >> 1, 0, 0
    for b in range(l, -1, -1):
        r <<= 1
        t = 1 << b
        u = s + t
        v = u << b
        if x < v:
            continue
        x -= v
        r |= 1
        s = u + t
    return (r, x)



def main():
    import argparse

    parser = argparse.ArgumentParser()
    parser.add_argument('N', type=int)
    args = parser.parse_args()

    print(args.N, '=', ' * '.join('%d^%d' % q for q in factor(args.N)))


if __name__ == '__main__':
    main()

実行結果

$ python3 sample.py 1234567890
1234567890 = 2^1 * 3^2 * 5^1 * 3607^1 * 3803^1