整数がらみで使いそうな関数まとめ(python)

最近Project Eulerを始めたおかげで整数関係の関数をいくつか作ったので、自分用にまとめておく。

素因数分解

#素因数分解
#[底, 指数]のリストを返す
def prime_factrization(n):
    prime_fact = []
    is_counting = False
    i = 2
    cnt = 0
    while i <= n:
        if n % i == 0:
            if not is_counting:
                is_counting = True
            cnt += 1
            n /= i
        elif n % i != 0:
            if is_counting:
                is_counting = False
                prime_fact.append([i, cnt])
                cnt = 0
            i += 1
    if is_counting:
        prime_fact.append([i, cnt])
    return prime_fact

約数の個数

上のprime_factrizationの返り値を用いている。

def count_divisor(n):
    prime_fact = prime_factrization(n)
    ret = 1
    for li in prime_fact:
        ret *= (li[1]+1)
    return ret

約数の総和

同上。

def sum_divisor(n):
    prime_fact = prime_factrization(n)
    ret = 1
    for li in prime_fact:
        t = 0
        for i in xrange(li[1]+1):
            t += li[0]**i
        ret *= t
    return ret