# permutations of eulers totient function

import math
import timeit
import collections
import itertools


start = timeit.default_timer()

def is_prime(x):
    if x == 2:
        return True
    if x == 1 or x % 2 == 0:
        return False
    for i in range(3,int(math.sqrt(x)) + 1,2):
        if x % i == 0:
            return False
    return True

def euler_70():
    divisors = [i for i in xrange(1000, 10000) if is_prime(i)]
    canidates = [i[0] * i[1] for i in itertools.combinations(divisors, 2) if i[0] * i[1] < 10000000]
    whole = collections.defaultdict(list)
    for n in canidates:
        for i in xrange(3, int(math.sqrt(n)) + 1, 2):
            if n % i == 0 and is_prime(i):
                whole[n].append(i)
        if len(whole[n]) == 1:
            whole[n].append(n / whole[n][0])
    low = 10000000
    low_N = 0
    for k in whole.keys():
        total = k
        for v in whole[k]:
            total *= ((float(v) - 1) / v)
        if sorted([i for i in str(k)]) == sorted([i for i in str(int(total))]):
            if float(k) / total < low:
                low = float(k) / total
                low_N = k
    return low_N

print "Answer: %s" % euler_70()
stop = timeit.default_timer()
print "Time: %f" % (stop - start)


@@ -69,27 +69,24 @@
 %0Aimport 
-collections
+operator
 %0Aimport 
@@ -95,16 +95,35 @@
 ertools%0A
+import collections%0A
 %0A%0Astart 
@@ -370,34 +370,39 @@
 def 
-euler_70():%0A    divisors =
+build_primes(limit):%0A    return
  %5Bi 
@@ -421,19 +421,20 @@
 nge(
-1000, 10000
+2, limit + 1
 ) if
@@ -446,16 +446,123 @@
 rime(i)%5D
+%0A%0Adef build_canidates(start, end, primes):%0A    divisors = filter(lambda x: %7Bx%7D & primes, range(start, end))
 %0A    can
@@ -571,27 +571,21 @@
 ates = %5B
-i%5B0%5D * i%5B1%5D
+%5D%0A   
  for i i
@@ -625,160 +625,205 @@
 , 2)
- if i%5B0%5D * i%5B1%5D %3C 10000000%5D%0A    whole = collections.defaultdict(list)%0A    for n in canidates:%0A        for i in xrange(3, int(math.sqrt(n)) + 1, 2):%0A    
+:%0A        product = reduce(operator.imul, i)%0A        if product %3C 10**7:%0A            canidates.append(product)%0A    return canidates%0A%0Adef calculate_phi(n, primes):%0A    base = n%0A    for i in primes:%0A
     
@@ -829,17 +829,20 @@
      if 
-n
+base
  %25 i == 
@@ -846,167 +846,194 @@
 == 0
- and is_prime(i):%0A                whole%5Bn%5D.append(i)%0A        if len(whole%5Bn%5D) == 1:%0A            whole%5Bn%5D.append(n / whole%5Bn%5D%5B0%5D)%0A    low = 
+:%0A            n *= (1 - (1 / float(i)))%0A    return n%0A%0Adef euler_70():%0A    primes = build_primes(10000)%0A    canidates = build_canidates(
 1000
+, 1
 0000
-%0A    low_N =
+, set(primes))%0A    low_phi, low = 10**7,
  0%0A 
@@ -1043,113 +1043,114 @@
 for 
-k
+n
  in 
-whole.keys():%0A        total = k%0A        for v in whole%5Bk%5D:%0A            total *= ((float(v) - 1) / v)
+canidates:%0A        factor = int(math.sqrt(n))%0A        phi = calculate_phi(n, primes%5B:factor%5D)        
 %0A   
@@ -1168,27 +1168,14 @@
 ted(
-%5Bi for i in 
 str(
-k)%5D
+n)
 ) ==
@@ -1186,28 +1186,16 @@
 ted(
-%5Bi for i in 
 str(int(
 tota
@@ -1194,16 +1194,13 @@
 int(
-total
+phi
 ))
-%5D
 ):%0A 
@@ -1217,30 +1217,25 @@
  if 
-float(k) / total
+n / phi
  %3C low
+_phi
 :%0A  
@@ -1255,53 +1255,30 @@
  low
- = float(k) / total%0A                low_N = k
+_phi, low = n / phi, n
 %0A   
@@ -1292,10 +1292,8 @@
  low
-_N
 %0A%0Apr

Clean up code by splitting function