Largest prime below a given number N

This came up as a part of algorithm puzzles:
Given a number $N$, how to find the prime $P$ such that $P<N$ and the difference $N-P$ is minimum.
For small $N$, simple sieves do work, but I’m unable to find solution for large values of $N$.
I tried to modify the sieves to somehow look over large values only, didn’t get anywhere.
Any solutions/hints for this?

Solutions Collecting From Web of "Largest prime below a given number N"

Start counting downward from $N-1$ After trial division by some small primes, you can use one of a number of probabilistic tests like the Fermat primality test. If $p$ is prime, $a^{p-1} \equiv 1 \pmod p$. This can be checked quickly. If it is true for a few $a$, the chance of $p$ being composite is very small. If you insist on certainty, you can finish up with one of the deterministic tests.