# What is the most efficient algorithm to find the closest prime less than a given number $n$

Problem
Given a number n, $2 \leq n \leq 2^{63}$. $n$ could be prime itself. Find the a prime $p$ that is closet to $n$.

Using the fact that for all prime $p$, $p > 2$, $p$ is odd and $p$ is of the form $6k + 1$ or $6k + 5$, I wrote a for-loop checking from $n - 1$ to 2 to check if that number is prime. So instead of checking for all numbers I need to check for every odd of the two form $p \equiv 1 \pmod{k}$, and $p \equiv 5 \pmod{k}$. However, I wonder if there is a faster algorithm to solve this problem? i.e. some constraints that can restrict the range of numbers need to be checked? Any idea would be greatly appreciated.

-
Use a strong probabilistic test and then verify primality with a deterministic test, e.g. see primes.utm.edu/prove/index.html – Bill Dubuque Apr 27 '11 at 0:38
Would storing all the primes within the range to some array and using (a suitably modified) binary search be impractical? – J. M. Apr 27 '11 at 0:40
You only have to check the interval $[n/2,2n]$ because of Bertrand's postulate. – lhf Apr 27 '11 at 0:53
@Chan: You will just be wasting a lot of people's time by asking in multiple places. If you are looking for different solutions you should mention that in your question. Also, disagree that you won't find good practical answers here. IMO, you will find much better answers (if needed, using 'bitwise') here than on stackoverflow. – Aryabhata Apr 27 '11 at 2:05
I think it's OK to ask (essentially) the same question in two venues, $\bf\ as\ long\ as\ you're\ upfront\ about\ it$, that is, as long as in each venue you note that you're asking it in the other, and you give a link so people can easily check to see that they are not duplicating effort. – Gerry Myerson Apr 27 '11 at 5:14

This is an extension of Bill's comment.

It is certainly reasonable to use strong probabilistic tests and then verify with the AKS algorithm. In fact, if we look for primes alternately above and below the target number and test with AKS, where each primality test takes time at most $log^{O(1)}N$, and there is an approximately $\dfrac{1}{logN}$ chance that each is prime, one would be at least 99% sure to find a prime in time $O(log^{O(1)}N)$. But this is not deterministic - conceivably, there exists an interval where this works very poorly, far worse than logarithmic time. To be fair, I suspect such an interval does not exist in the numbers up to $2^{64}$. But speaking generally, a deterministic algorithm might be desired.

To that end, I refer you to the results of Polymath4 "Finding Primes," a collaborative mathematical experience that sought to find a method to deterministically find primes of about a given size. In their paper, they describe deterministic methods that take time $O(N^{.5 + \epsilon})$, which I think is pretty exciting.

Ultimately, I would say that Bill's suggestion of probabilistically checking numbers and then verifying their primality is optimal. But the promise of a deterministic algorithm is... quite alluring, I think, too.

-
Just a note: The gain by using probabilistic primality test is that if a number is deemed composite, we can ignore running the deterministic test on it, as usually probablisitic tests don't lie about compositeness. – Aryabhata Apr 27 '11 at 2:18
This is very clear! Whenever I find primes of a large size, I always just search using Miller-Rabin and AKS. But it is still probabilistic, not deterministic. – mixedmath Apr 27 '11 at 2:31
@mixed: Most probabilistic tests guarantee compositeness (I believe Miller-Rabin is one of those). So using Miller-Rabin then AKS is a deterministic algorithm! – Aryabhata Apr 27 '11 at 2:55
@mixed: There are many determinstic algorithms whose runtime is not known precisely. Shell Sort is one classic example. Deterministic does not mean you know the runtime. It just means you are 100% confident of the output. The whole point of using a probabilistic test is that we will likely move over the composites quickly and only run AKS on some composites and primes saving a lot of computation time. – Aryabhata Apr 27 '11 at 3:05
@mixed: Come on. You know very well it does not matter if it was AKS or not :-) Anyway, I agree that it is not determinstic with respect to the runtime, but it is determinstic with respect to the output. We are talking of different things I suppose. Anyway... – Aryabhata Apr 27 '11 at 3:22

You mention $2^{63}.$ It's known that below $4\cdot10^{18}\approx2^{61.8},$ there is at least one prime every 1476 numbers. So a reasonable algorithm would be to sieve some numbers smaller than n (up to 2000 if you want to be on the safe side) up to some small bound, then check the remaining numbers with the Miller-Rabin test. Test any that pass with a primality-proving algorithm—do not use AKS as other answers have suggested; it is not fast in this range.

Of course 2000 is overkill; an interval of length 200 should be good enough for 99.9997% of cases. But sieving is fast so it's not really obvious what length is optimal. In any case the more important optimization issue is deciding how far to sieve rather than how long of an interval to sieve.

As for the primality-proving algorithm, ECPP works. Recently it was proven that there are no BPSW-pseudoprimes less than $2^{64},$ so a Lucas test following your MR test (to base 2) is even faster.

-
using a segmented seive upto root of n would be a good optimization . – saru95 Jun 11 at 10:45
@saru95 I don't think so, not at that size. Faster to sieve out the easy composites and test the rest rather than doing billions of divisions. – Charles Jun 11 at 14:37

Use sieving to optimize your loop even more.

Guess an interval of reasonable length on which your prime is going to be found. Initialize a corresponding table with entries all equal to "true".

Go over a list of small primes $p_i$, and compute $n \mod p_i$. Using that value, you can mark off some of the entries in the table as "false".

Now do what Bill suggests - go over the remaining entries, use Miller-Rabin and then if you want to be really sure, some deterministic test (not necessarily AKS, which is slow).

-
Thanks a lot ;) – Chan Apr 27 '11 at 0:53
"p_i \mod n" -> "n \mod p_i"? – Douglas S. Stones Apr 27 '11 at 2:28
Corrected, thanks Douglas. – Yuval Filmus Apr 27 '11 at 12:53