6
$\begingroup$

Are there any good algorithms which can be used to construct a prime greater than $n$, for arbitrary $n$?

There are some brute force approaches: for example, factoring $n!+1$. However, I'm looking for something significantly more efficient; preferably, polynomial in $n$.

Also, if anyone knows of a proof showing a bound on the speed of such an algorithm (say, $n^4$), I would like to hear about it.

EDIT: It appears that polynomial in $\ln(n)$ makes more sense.

$\endgroup$
8
  • $\begingroup$ If $n$ is odd, keep incrementing by 2 for as long as a test for compositeness returns true. If $n$ is even, add 1 first before using the procedure for odd $n$. $\endgroup$
    – J. M. ain't a mathematician
    Dec 22, 2010 at 2:34
  • 2
    $\begingroup$ Will any prime do? Or are you looking for the least such prime? In any case, see this previous question: math.stackexchange.com/questions/8865/… $\endgroup$
    – Aryabhata
    Dec 22, 2010 at 2:36
  • $\begingroup$ I am unsure whether to close this as a dupe, there could be faster algorithms if any prime is sought. (For instance if we knew an upper bound for $n$, we could just hardcode it). $\endgroup$
    – Aryabhata
    Dec 22, 2010 at 2:45
  • $\begingroup$ Trial division requires sqrt(n) queries "does m divide n?" (which can be tested in O(log n) time by Euclid's algorithm). There is always a prime between n+1 and 2(n+1). Hence, we can always find a prime greater than n in O(n*sqrt(n)*log n) time using J.M.'s algorithm. [you're probably after polynomial in log n] $\endgroup$
    – Douglas S. Stones
    Dec 22, 2010 at 2:48
  • 3
    $\begingroup$ I think you mean factoring n! + 1. $\endgroup$
    – Qiaochu Yuan
    Dec 22, 2010 at 2:52

4 Answers 4

Reset to default
6
$\begingroup$

Well theoretically speaking, there is a deterministic $\mathcal{O}(n \log ^{12} n)$ time algorithm.

By Bertrand's postulate, there is a prime $p$ guaranteed to satisfy $n \le p \lt2n$. (In practice, you should hit one much earlier than $2n$, owing to the prime number theorem).

Use the AKS primality testing program to test each of the numbers in the range $[n, 2n)$ and you will find one.

You can also try some sieving etc as suggested in the answers to this other question here: The least prime greater than 2000

$\endgroup$
3
  • $\begingroup$ It's been a while since I last looked into this subject (which was the time AKS was first published XD ): is AKS practical nowadays? $\endgroup$
    – J. M. ain't a mathematician
    Dec 22, 2010 at 2:55
  • $\begingroup$ @J.M: I believe they got it down to $\log^6 n$, but I have heard it is still impractical. That is why I specifically said "theoretically speaking..." :-) $\endgroup$
    – Aryabhata
    Dec 22, 2010 at 2:56
  • $\begingroup$ The time can be decreased to $O(n^{0.525+\varepsilon})$ due to Baker-Harman-Pintz 2001. $\endgroup$
    – Charles
    Sep 15, 2011 at 18:04
3
$\begingroup$

Terence Tao has set up a "polymath project" which addresses exactly your question. Here is the relevant page:

http://michaelnielsen.org/polymath1/index.php?title=Finding_primes

It contains a list of conjectures, partial results and references. To sum it all up: At the moment the answer to your question is No.

$\endgroup$
1
$\begingroup$

There is an algorithm of complexity $O((\ln n) \cdot P(n))$ where $P(n)$ is the complexity of computing the prime counting function on n (usually denoted $\pi(n)$).

By Bertrand's postulate there is a prime in the interval $[n,2n]$ so you can do a binary search on it:

If $\pi\left(n+\frac{n}{2}\right)-\pi(n)$ > 1 there is a prime in the interval $\left[n, n+\frac{n}{2}\right]$, otherwise there is a prime in the interval $\left[n+\frac{n}{2}+1,2n\right]$ and so you obtain a smaller interval that contains a prime. Repeat the calculation on the new interval. The calculation for which of the 2 intervals to use needs time $O(P(n))$. Since each interval is half the size of the previous one the total number of calculations required is O(ln n).

Odlyzko's algorithm for $\pi(n)$ has complexity $O(n^{\frac{1}{2}})$. There is a link to a short description of it on the polymath page. So the overall complexity of this algorithm is $O((\ln n)n^{\frac{1}{2}})$.

$\endgroup$
1
  • 1
    $\begingroup$ Isn't it $O(n^{0.5+\varepsilon})$? In that case the $\varepsilon$ subsumes the $\log n$ term entirely. $\endgroup$
    – Charles
    Sep 15, 2011 at 18:07
0
$\begingroup$

Polynomial in $n$ is not efficient because the input length (measured in bits) is $\log_2 n$ and so $n$ is exponentially large in relation to your input length.

So it is easy to find a prime number greater than $n$ in time polynomial in $n$ (e.g. with the answer from Moron).

If you are interested in a deterministic algorithm than the polymath project gives you the current known results.

But there is a randomized algorithm with time polynomial in $\log_2 n$ that gives you a prime greater than $n$. You pick a random number from the set $n, \ldots, 2n$ and check this number with AKS or Miller Rabin primality test. With the prime number theorem you can proof that there are enough primes in the set (for large $n$) and if you repeat this algorithm $O(\log_2 n)$ times you find a prime with high probability.

At the moment I cannot find a reference for a detailed proof for the randomized algorithm. But if you are interested I can look for it when I have more time.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .