projecteuler solution 69

1 files changed, 28 insertions, 0 deletions

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
+