# Euler's totient function maximum value for a range [duplicate]

For the euler's totient function, we have a number $n<10^{18}$

we have to find the value of $i$ between $2$ and $n$ (both inclusive) such that the value of $\phi(i)/i$ is maximum.

I have have observed that this value will be equal to the largest prime number less than or equal to n. Now since $n$ is upto $10^{18}$, what will be the most efficient way to do this?

## marked as duplicate by Marc van Leeuwen, Dennis Gulko, Davide Giraudo, Julian Kuelshammer, azimutMay 5 '13 at 9:55

$\phi(p)=p-1$, so now you have to look for largest prime before $10^{18}$
• Even for $i=p^m$, $\phi(i)/i=(p-1)/p$, so need to look for primes and prime powers! – Karthik C May 5 '13 at 8:31
• @AneeshKarthikC: When $i=p^m$, $\phi(i)=p^m(\dfrac{p-1}{p})$, right? – Inceptio May 5 '13 at 8:34
• $\phi(i)/i$ I remarked about – Karthik C May 5 '13 at 8:42