k_powerful integers

k_powerful.py

def kpowerful(k, upper_bound, count = True):
    '''
    Inspired by https://rosettacode.org/wiki/Powerful_numbers#Python
    '''
    def prime_powers(k, upper_bound):
        ub = int(math.pow(upper_bound, 1/k) + .5)
        res = [(1,)]
        for p in list_primes(ub):
            a = [p**k]
            u = upper_bound // a[-1]
            while u >= p:
                a.append(a[-1]*p)
                u //= p
            res.append(tuple(a))
        return res
    ps = prime_powers(k, upper_bound)
    l = len(ps)
    def generate(primeIndex, ub):
        if count:
            res = 0
        else:
            res = []
        for p in ps[primeIndex]:
            u = ub//p
            if not u:
                break
            if count:
                res += 1
            else:
                res += [p]
            for j in range(primeIndex + 1, l):
                if u < ps[j][0]:
                    break
                if count:
                    res += generate(j, u)
                else:
                    res += [p*x for x in generate(j, u)]
        return res
    if count:
        return generate(0, upper_bound)
    else:
        return sorted(generate(0, upper_bound))