# 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?

• Off the top of my head: Let $m$ the product of some initial segment of primes (how many would depend on the size of $N$). For example, $m=2\cdot3\cdot5\cdot7\cdot11\cdot13=30030$. Make an list of all the numbers below $m$ with $\gcd(m,x)=1$. This list can be quickly used to pick non-multiples of the prime factors of $m$ in any segment of numbers. Now start at $N-1$ and move downwards, checking the candidates in turn. – Harald Hanche-Olsen May 3 '13 at 17:08
• When you have a candidate, if $N$ is very large use a probabilistic primality test such as Miller–Rabin first, then follow up with a proper proof of primality if that is required. – Harald Hanche-Olsen May 3 '13 at 17:10
• This counting down can be painful. If candidates can be enumerated fast, that'll be nice – Avogadro May 3 '13 at 17:32
• Enumerating candidates fast is what the first part was all about. – Harald Hanche-Olsen May 3 '13 at 18:12
• what for large N (say $10^{16}$), there the reduced complexity in search space still seems impractical – Avogadro May 3 '13 at 18:47

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.
• @Avogadro: The trial division can help a lot. Even $2,3,5$ eliminate all but 8 out of 30. You can make a list of the moduli that are acceptable and avoid the trial divisions. – Ross Millikan May 3 '13 at 18:07
• what for large N (say $10^{16}$), there the reduced complexity in search space still seems impractical. (sorry for copy-pasting comments from top again :) ) – Avogadro May 3 '13 at 18:48
• @Avogadro: around $10^{16}$ about one in $37$ numbers is prime, so if you use the $\pmod {30}$ restriction, you should only have to try $10$ on the average. I don't think that is bad. – Ross Millikan May 3 '13 at 19:13
• As an aside, if you're used to using primes for public-key cryptography then primes around $10^{16}$ are pitifully small. – Harald Hanche-Olsen May 3 '13 at 23:53