Project Euler 88

プロジェクトオイラー
http://projecteuler.net/index.php

Q88.
k個の自然数の和と積が等しいとき、和積数と呼ぶ。kに対する和積数の最小値の2≤k≤12000での総和

この問題ではじめて正答数が3桁になった。いよいよ問題が難しくなってくる。
kでなく、和積から調べていく。和積に対して、再帰的にそのような組合せがあるか調べる。あれば、kが求まるから、そのkに対してすでに和積があるか見て、なければ総和に加える。

from math import sqrt, log

from itertools import ifilter
def sum_product(n):

    for p in range(2, int(sqrt(n + 0.5) + 1)):

        if n % p == 0:

            for s in sum_product(n / p):

                yield (s[0] + 1, s[1] + p)

    yield (1, n)
def gen_primes(a):

    for q in range(3, int(sqrt(N + 0.5)) + 1, 2):

        for p in a:

            if p * p > q:

                a.append(q)

                break

            if q % p == 0:

                break
def make_sum_product(n):

    found = False

    for s in sum_product(n):

        if s[0] == 1:

            continue

        k = n + s[0] - s[1]

        if k <= N and a[k] == 0:

            a[k] = n

            found = True

    return found
N = 12000

M = N * 2

a = [ 0 for i in range(N + 1) ]

print sum(ifilter(make_sum_product, xrange(2, M + 1)))