phi(n) = n * product(1-1/p for all primes p if p|n) therefore: n/phi(n) = product(p/(p-1) for all primes p if p|n)

Since p/(p-1) is larger for smaller values of p, it is reasonable to assume (and it can be proved) that the answer n will always be the largest product of the first r primes such that the product is less than N.

You only need the first 16 primes to reach a product greater than 10^18 so only the first 15 primes (the largest being 53) are needed.

Sieve the primes up to 53. Sort the test inputs N (preserving the order somewhere so you can output them in the correct order) and simply begin multiplying primes until you get past the next N. Store the value previous to the last multiplication and continue untill all N values have theri associated answer.

kitchent asked how we would answer if n/phi would also be needed: as you multiply primes, also multiply p/(p-1) to a seperate variable that stores the n/phi(n) ratio.

100 points. Implemented @leduckhai 's algorithm in Python 3.

sieve=[True]*10**3
for i in range(0,10**3,2):
    sieve[i]=False
for j in range(3,int(10**3)+1,2):
    if sieve[j]:
        for k in range(j*2,10**3,j):
            sieve[k]=False
sieve[1],sieve[2]=False,True
def totient(n):
    m=1
    ans=0
    for i in range(1000):
        if sieve[i]:
            if m*i>=n:
                return m
            else:
                m=m*i
                ans+=i//(i-1)

t=int(input().strip())
for _ in range(t):
    n=int(input().strip())
    print(totient(n))

I draw a diagram which shows step-by-step solution here

Hope it helps you understand easier

hint:- if we see here from the description table ,the prime no. has more no. of relative primes. 1 is considered as relative prime for every no. for n/phi(n) should be large ,phi(n) should be small and n should be large. just consider n as product of prime no.and check whether its smaller than the given limit. phi(n)=n*(1-(1/p)), where p is prime.

attention : if p is prime p^k/phi(p^k) = p^(k-1)/phi(p^(k-1))=...= p/p-1;