From 6ef421d976109c4f4c71a671f24355ce858b3e0c Mon Sep 17 00:00:00 2001
From: Reiner Herrmann <reiner@reiner-h.de>
Date: Sun, 27 Jun 2010 02:00:52 +0200
Subject: projecteuler solution 69

---
 src/projecteuler/069.py | 28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)
 create mode 100644 src/projecteuler/069.py

diff --git a/src/projecteuler/069.py b/src/projecteuler/069.py
new file mode 100644
index 0000000..99236c5
--- /dev/null
+++ b/src/projecteuler/069.py
@@ -0,0 +1,28 @@
+from common import sieve
+
+primes = sieve(1000000).primes()
+prime_list = [ p for p in primes if p < 1000 ]
+prime_list.sort()
+
+def phi(x):
+	if x in primes:
+		return x-1
+	product = x
+	for p in prime_list:
+		if p*p > x:
+			break
+		if x % p != 0:
+			continue
+		product *= (1 - 1/float(p))
+	return product
+
+maxn = 0
+maxres = 0
+
+for n in xrange(2, 1000001):
+	if n/phi(n) >= maxres:
+		maxres = n/phi(n)
+		maxn = n
+
+print maxn
+
-- 
cgit v1.2.3