phi cache

import collections
import functools
import operator

def prod(a, one=1):
    return functools.reduce(operator.mul, a, one)

def many_phi(n):
    facts = [collections.Counter() for _ in range(n)]
    for i in range(2, n):
        if not facts[i]:
            k = i
            while k < n:
                for j in range(k, n, k):
                    facts[j][i] += 1
                k *= i
    phi_facts = [sum((sum((facts[i] for _ in range(j-1)), collections.Counter())+facts[i-1]
        for i, j in c.items()), collections.Counter()) for c in facts]
    phis = [prod(j**k for j, k in i.items()) for i in phi_facts]
    phis[0] = 0
    return phis