It is a programming question but mathematics has a major role to play in it. I have to find the largest prime less than a number $n$. Note that $n\leq10^{18}$. I can go for Fermat's Little Theorem which runs in $O(\log n)$ time and then check whether the number is prime or not by checking for existence of its divisors from $2$ to $\sqrt n$. But this will take $O(\sqrt n)$ time which is way beyond the machine's capability.
So how do I make Fermat's Little Theorem ultimate i.e. what are the values I'll need to run FLT with to ensure that it is prime or composite without having to go through $O(\sqrt n)$ operations?