Python で素因数分解と約数を求める。

リストにして返します。

$ python sample.py 
# n
630
# 素因数
(2, 1)
(3, 2)
(5, 1)
(7, 1)
# 約数
[(2, 0), (3, 0), (5, 0), (7, 0)] 1
[(2, 0), (3, 0), (5, 0), (7, 1)] 7
[(2, 0), (3, 0), (5, 1), (7, 0)] 5
[(2, 0), (3, 0), (5, 1), (7, 1)] 35
[(2, 0), (3, 1), (5, 0), (7, 0)] 3
[(2, 0), (3, 1), (5, 0), (7, 1)] 21
[(2, 0), (3, 1), (5, 1), (7, 0)] 15
[(2, 0), (3, 1), (5, 1), (7, 1)] 105
[(2, 0), (3, 2), (5, 0), (7, 0)] 9
[(2, 0), (3, 2), (5, 0), (7, 1)] 63
[(2, 0), (3, 2), (5, 1), (7, 0)] 45
[(2, 0), (3, 2), (5, 1), (7, 1)] 315
[(2, 1), (3, 0), (5, 0), (7, 0)] 2
[(2, 1), (3, 0), (5, 0), (7, 1)] 14
[(2, 1), (3, 0), (5, 1), (7, 0)] 10
[(2, 1), (3, 0), (5, 1), (7, 1)] 70
[(2, 1), (3, 1), (5, 0), (7, 0)] 6
[(2, 1), (3, 1), (5, 0), (7, 1)] 42
[(2, 1), (3, 1), (5, 1), (7, 0)] 30
[(2, 1), (3, 1), (5, 1), (7, 1)] 210
[(2, 1), (3, 2), (5, 0), (7, 0)] 18
[(2, 1), (3, 2), (5, 0), (7, 1)] 126
[(2, 1), (3, 2), (5, 1), (7, 0)] 90
[(2, 1), (3, 2), (5, 1), (7, 1)] 630


参考にしたサイトは、こちら。
素因数分解

def usage():
    n = 2 * 3**2 * 5 * 7
    print(n)
    for e in (factorize(n)):
        print(e)
    for e in aliquot((factorize(n))):
        print(e, num(e))


def factorize(n):
    s = int(n ** 0.5)
    fct = []
    k = n
    for b in range(2, s + 1):
        e = 0
        while k % b == 0:
            e = e + 1
            k = k // b
        if e != 0:
            fct.append((b, e))
    if k > s:
        fct.append((k, 1))
    return fct


def aliquot(fct):
    alq = []
    if not fct:
        alq.append([])
        return alq
    base, exponent = fct.pop()
    pre_alq = aliquot(fct)
    suf_alq = [[(base, e)] for e in range(exponent + 1)]
    for pre in pre_alq:
        for suf in suf_alq:
            alq.append(pre + suf)
    return alq


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a


if __name__ == '__main__':
    usage()
Remove all ads