Project Euler 29（1）

Problem 29
（略）a^b 2 ≤ a ≤ 100, 2 ≤ b ≤ 100で生成される数列で異なる項はいくつあるか。
http://projecteuler.net/index.php?section=problems&id=29

Pythonなら100¹⁰⁰も簡単に計算できるので、そのまま書けば答えは出てきます。

from itertools import product
N = 100

print len(set(map(lambda x: x[0] ** x[1],

        product(range(2, N + 1), repeat = 2))))

しかし、N=1000とするとメモリが足りなくなります。
素因数分解して計算することにしましょう。そうすれば大きな数の計算をしなくて済みます。例えば、12なら( (2, 2), (3, 1) )とします。そうすると、12¹⁰⁰は( (2, 200), (3, 100) )となります。

from itertools import product
def calc_exp(n, p):

    e = 0

    while n % p == 0:

        e += 1

        n /= p

    return e, n
def gen_factorize():

    a = range(N + 1)

    b = [ () for n in a ]

    for p in range(2, N + 1):

        if len(b[p]) == 0:

            for q in xrange(p, N + 1, p):

                e, a[q] = calc_exp(a[q], p)

                b[q] = b[q] + ( (p, e), )

    

    for n in range(2, N + 1):

        if a[n] != 1:

            b[n] = b[n] + ( (a[n], 1), )

        yield b[n]
def pow_f(f, e):

    return tuple(map(lambda x: (x[0], x[1] * e), f))
N = 1000

print len(set(map(lambda x: pow_f(x[0], x[1]),

        product(gen_factorize(), range(2, N + 1)))))

しかし、これもメモリをかなり使ってしまい、これよりNを大きくできないようです。
そこで、次にProject EulerのProblem 1と同じような考え方を使いましょう。