def totient(lim):
    """Computes Euler's totient for values up to lim included."""
    # http://en.wikipedia.org/wiki/Euler%27s_totient_function
    tot = list(range(lim + 1))
    tot[0] = -1
    for i in range(2, lim + 1):
        if tot[i] == i:
            for j in range(i, lim + 1, i):
                tot[j] = (tot[j] * (i - 1)) // i
    return tot