# Euler Problem 69

I tried this first with a GCD function and found it too slow. In fact it would have taken nearly a month to run. So I looked for a more efficient algorithm. Surprisingly, I found this one in Java (ironic isn’t it?) then translated it to Python. I must admit, working out Euler Problems is a bit easier with Python. I suppose manipulating lists etc. in a higher level scripting language requires less work. Java was a bit too system-level for this kind of work. So this routine is pretty slick. It runs through the entire set in under 90 seconds. Next.

```#Euler69
def totient(n):
result = float(n)
i = 2
while i*i <= n:
if n % i == 0:
result -= result/i
while n % i == 0:
n /= i
i += 1
if n > 1:
result -= result/n
return result
print "Crunching Phi's\n"
max_n = 0
max_n_div_phi = float(0)
for n in range(2,1000001):
phi = totient(n)
n_div_phi = float(n/phi)
if n_div_phi > max_n_div_phi:
max_n = n
max_n_div_phi = n_div_phi
print "n:"+str(n)+" phi:"+str(phi)+" n/phi:"+str(n_div_phi)
if n % 100000 == 0:
print "Testing "+str(n)+"s"
print "\nAnswer: Value of n with max_n_div_phi is "+str(max_n)
```