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