From here, I found that phi(N)/N will be maximum, when the number of prime factors is minimum (which is equal to 1); and when this prime factor is maximum. This clearly means I need the largest prime less than or equal to the given N.
To check whether a number is prime, I used the Miller-Rabin test, the details of which I took from here. But how many iterations? From citation number 12 in the given link, I reached here. From this, I got all my requirements. These finally led me to this Python code:
def modular_pow(base, exponent, modulus):
result = 1
while exponent > 0:
if (exponent % 2 == 1):
result = (result * base) % modulus
exponent = exponent // 2
base = (base * base) % modulus
return result
def passesMillerRabinTest(n, a):
s = 0
d = n - 1
while (d % 2 == 0):
s += 1
d >>= 1
x = modular_pow(a, d, n)
if (x == 1 or x == n - 1):
return True
for ss in xrange(s - 1):
x = (x * x) % n
if x == 1:
return False
if x == n - 1:
return True
return False
primeList = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37)
def isPrime(n):
for p in primeList:
if n % p == 0:
return n == p
for p in primeList:
if passesMillerRabinTest(n, p) == False:
return False
return True
t = int(raw_input())
for tt in xrange(t):
n = int(raw_input())
if n == 2:
print 2
continue
if n % 2 == 0:
n -= 1
while (True):
if isPrime(n):
print n
break
n -= 2
And, it was AC!!
