# Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$

I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.

I tried this approach , but is too slow. Finding the just smallest prime number to $N$, as its $\frac{\phi(i)}{i}$ value is $\frac{i-1}{i}$, which is maximum in the range. (See Maximum of ϕ(i)i\frac{\phi(i)}i)

So, I was wondering if there is any other faster way to find the maximum value. More precisely I need the value of i where $\frac{\phi(i)}{i}$ is maximum.

Since you know that the maxium value is achieved when $i$ is the largest prime smaller than $N$, your problem is equivalent to finding the largest prime smaller than $N$.
There are many ways to test for primality, so presumably you could just take your favorite primality test and run a for loop from $N-1$ downwards, to find the first number which is prime.
• Surely it still makes sense to skip over all even numbers? There is a tradeoff here. While the primality testing algorithm is fast, you'll have to test around $\log N$ integers until you actually find a prime. – Yuval Filmus May 8 '13 at 13:34