Cleaner Euler Phi Function

phi.py

import collections

def next_div(n):
    for i in xrange(2, n):
        if (n % i == 0):
            return i
    
    return n

# d | n, d is prime
def elim(n, p):
    c = 0

    while (n % p == 0):
        n /= p
        c += 1

    return n, c

# n >= 2
def fact(n):
    f = collections.Counter()

    while (n != 1):
        p = next_div(n)
        n, f[p] = elim(n, p)

    return f

def phi(f):
    r = 1

    for b, e in f.iteritems():
        r *= (b - 1)*b**(e - 1)

    return r

def phi_of(n):
    return phi(fact(n))

print phi_of(123456)