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.

Perhaps I do not understand what you are asking for.

• I tried this approach using Miller-Rabin but it takes 1 minute on my system for 10^18. So, I was looking for any other faster way of finding. – user7711 May 8 '13 at 9:57
• Use sieving first to dramatically improve your running time. – Yuval Filmus May 8 '13 at 13:22
• @YuvalFilmus, seiving algorithm is dramatically slower than Miller-Rabin in this case, because he just need one number, also his test was wrong, I suggest a very fast prime algorithm for him, but he added very bad implementation to the algorithm. cs.stackexchange.com/questions/11883/… – user742 May 8 '13 at 13:26
• 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
• @YuvalFilmus, anyway I updated my answer there, but for other readers, when you know the bound you can skip the pseudoprime numbers for specific range, and for this range there are just 8 forbidden number to take care of them, so is constant number of iteration after Miller-Rabin. – user742 May 8 '13 at 14:05