problem_72.py

from math import sqrt

d = pow(10, 6)
factors = [-1, -1] 
primes = []

def phi(i):
   res = 1 
   index = 0 
   while index < len(factors[i]):
      k = len([0 for f in factors[i] if f is factors[i][index]])
      res *= pow(factors[i][index], k)*(1-1./factors[i][index])
      index += k
   return int(round(res))

# Generates factors and primes <= d
def generate():
   for i in xrange(d+1):
      p = 0 
      while p < len(primes) and primes[p] <= int(sqrt(i))+1:
         if i % primes[p] == 0: # No prime
            factors.append(factors[i / primes[p]] + [primes[p]])
            break
         p += 1
      if len(factors) == i: # Prime
         primes.append(i)
         factors.append([i])

generate()
ans = 0 
for i in xrange(2, d+1):
   ans += phi(i)
print "The answer is: " + str(ans)