blob: 99236c544f9a3b6bb4edcba4b54d67a08592f9a6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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
|
