約数

約数の個数

自然数の約数（divisor）は、素因数分解されていると簡単に求まります。まず、8の約数は、2³だから、2をいくつ選ぶかで決まります。すなわち、0〜3個のうちどれかを選ぶことになります。

1 = 2⁰
2 = 2¹
4 = 2²
8 = 2³

ですから、8の約数の個数は4です。
次に24を考えましょう。24 = 2³ • 3¹ですが、約数を列挙すると次のようになります。

1 = 2⁰ • 3⁰
2 = 2¹ • 3⁰
4 = 2² • 3⁰
8 = 2³ • 3⁰
3 = 2⁰ • 3¹
6 = 2¹ • 3¹
12 = 2² • 3¹
24 = 2³ • 3¹

24は素因数に2と3を持つので、約数は2と3を独立にいくつ選ぶかで決まります。2は4通り、3は2通り選べるので、8通り選べる、すなわち約数の個数は8となります。
一般に、

n = p₁^e₁ … p_m^e_m

とすると、nの約数の個数は、

(e₁ + 1) … (e_m + 1)

となります。

# factorizeは下参照

def num_divisors(n):

    return reduce(lambda x, y: x * (y[1] + 1), factorize(n), 1)
print num_divisors(24)

約数の総和

まず、8の約数の総和は、

1 + 2 + 2² + 2³ = 2⁴ - 1

となります。
次に、24の約数の総和は、3で割り切れるかどうかで括って、

(1 + 2 + 2² + 2³) + 3(1 + 2 + 2² + 2³) = (2⁴ - 1)(3² - 1) / 2

一般に、

n = p₁^e₁ … p_m^e_m

とすると、nの約数の個数は、

(p₁^e₁+1 - 1) / (p₁ - 1) … (p_m^e_m+1 - 1) / (p_m - 1)

となります。

def sum_divisors(n):

    def f(x, y): return x * (y[0] ** (y[1] + 1) - 1) / (y[0] - 1)

    return reduce(f, factorize(n), 1)
print sum_divisors(24)

約数を列挙する

これも同様です。24ならまず、3から1と3が出ます。8から1,2,4,8が出るので、そこに1と3をそれぞれ掛けます。

def calc_exp(n, p):

    e = 0

    while n % p == 0:

        e += 1

        n /= p

    return e, n
def gen_prime_candidates():

    yield 2

    n = 3

    while True:

        yield n

        n += 2
def factorize(n):

    f = ()

    for m in gen_prime_candidates():

        if m * m > n:

            break

        e, n = calc_exp(n, m)

        if e:

            f = f + ( (m, e), )

    if n != 1:

        f = f + ( (n, 1), )

    return f
def gen_divisors(f, k = 0):

    if k == len(f):

        yield 1

    else:

        p, e = f[k]

        for d in gen_divisors(f, k + 1):

            for e1 in range(e + 1):

                yield p ** e1 * d
f = factorize(24)

for d in gen_divisors(f):

    print d