Tic Xenotation

tx.py

# 801693b1d56b19d77272b3c6db46a751
def primes(n):
    pfac = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            pfac.append(d)
            n //= d
        d += 1
    if n > 1:
        pfac.append(n)
    return pfac 


p=set([2])
for n in xrange(10000):
    for prime in primes(n):
        p.add(prime)
p=sorted(list(p))


def pdx(prime):
    return p.index(prime) + 1


def xenotate(n):
    in_ = [n]
    stack = []
    out = ''
    while len(in_) > 0:
        m = in_.pop()
        if m == 1:
            comp = ''
            for symbol in stack[::-1]:
                if symbol == ':':
                    comp += ':'
                else:
                    comp = '(' + comp + ')'
            out += comp
            stack = []
        elif m % 2 == 0:
            stack.append(':')
            in_.append(m // 2)
        else:
            decomp = primes(m)
            if len(decomp) == 1: # n is prime
                stack.append('()')
                in_.append(pdx(m))
            else:
                in_.extend(decomp)
    return out