Project Euler 29 別解

Q29.
abの形(2 ≤ a ≤ 100, 2 ≤ b ≤ 100)の整数の数

99*99=9801から重複する数を引く。
まず、aが2乗から6乗で表される整数に分ける(なるべく大きいべき乗に入れる)。そして、例えば4乗なら、a = c4として、a20 = c80、a72 = (c3)96などと、より小さい底で表すことができる。そういう数を引くことにする。
そうした処理をしたのが下のコード。もっと工夫できるとは思うが、とりあえず大きな数のべき乗の計算はせずに答えが出せている。



from math import log
from itertools import count

def has_key(k, pows, n):
for m in range(max_exp, n, -1):
if k in pows[m]:
return True
return False

def set_pows(pows, n):
pows[n] = set()
for m in count(2):
p = m ** n
if p > N:
break
if not has_key(p, pows, n):
pows[n].add(p)

def calc_duplication(n):
b = [ False for i in range(N + 1) ]
for d in range(1, n):
for k in range(2, N + 1):
m = k * d
p = m / n
if m % n == 0 and p >= 2:
b[p] = True
return len(filter(lambda x: x, b))

N = 100
max_exp = int(log(N) / log(2))
pows = [ [ ] for i in range(max_exp + 1) ]
for n in range(max_exp, 1, -1):
set_pows(pows, n)

npows = map(len, pows)

print (N - 1) ** 2 - reduce(lambda x, y: x + y,
map(lambda n: npows[n] * calc_duplication(n), range(max_exp, 1, -1)))