# The least prime greater than 2000

I'm a bit curious as to how "real" mathematicians would solve this problem.

"Find the least prime number greater than 2000."

Of course, I can always go brute force:

IF N IS PRIME, OUTPUT N
ELSE INCREASE N BY 1


But that's no fun. (Especially when the number is really high.)

Are there any algorithms/tricks/etc. that can help me solve this quickly and efficiently, especially if I were given large values of N?

-
Well, there's the prime-counting function that you can use for a starting point... –  Ｊ. Ｍ. Nov 4 '10 at 5:06
This is basic but, you only need to look at numbers whose last digit is 1,3,7 or 9. There are also a few digit division tricks as well (ie. if 3 divides the sum of the digits skip) from there on, use a sieve. –  a little don Nov 4 '10 at 5:11
@JohnSmith I think this is math.stackexchange.com, but maybe my browser has gone inexplicably evil, and is telling me it's math.stackexchange.com when it isn't really. –  muntoo Nov 20 '10 at 20:06
@muntoo. To understand recursion you first need to understand recursion. –  John Smith Nov 20 '10 at 22:45
@JohnSmith I know what recursion is. I still don't get what the point of your comment is. –  muntoo Nov 21 '10 at 0:47

I expect there are more powerful tools available; but for a simple approach I would apply the Prime Number Theorem (PNT) and a sieve (as Yuval has already suggested).

One useful consequence of the PNT is that around a number N, approximately one out of every log(N) numbers is prime. (By 'log,' number theorists always mean the natural log 'ln'.) So around 2000, about 1 out of every 7.6 numbers is prime. Let's just look among the numbers 2001 to 2060 for our next prime-- I'm leaving extra space in case a big prime gap happens to show up around 2000.

Now we use the sieve-- we can throw out all even numbers in our list, since they are certainly not primes. Next, we can throw out everything divisible by 3, then everything divisible by 5, by 7, by 11,... When should we stop sieving? We can stop when we get to $\sqrt{2060} \approx 45$, since if any number in our list can be factored as M = ab, then one of the factors must be less than or equal to the square root of the biggest number in our list.

Of course, a computer would be happy to do this process for you. But, I just wrote down the list and went through my basic sieve (primes up to 43); and I got the prime numbers 2003, 2011, 2017, 2027, 2029, 2039, 2053.

-
The PNT gives an easy way to estimate the average gap between primes around N, but a good estimate for the biggest possible prime gap around N seems to be much more difficult. (Several open conjectures in number theory are connected with this question.) The "worst" known prime gap, between two 19-digit primes, is over 35 times log(P). –  Jonas Kibelbek Nov 4 '10 at 8:21
Conventional wisdom suggests the largest prime gap below x is something like k log^2 x. Cramer's model suggests k = 1, Maier's more refined approach suggests k = 2/e^gamma = 1.229.... –  Charles Nov 4 '10 at 13:24
Be sure to read the answer from Charles as well. My approach is good for solving by hand on scrap paper or for a basic computer program. However, to find really big primes, I'm sure the method Charles gives is many, many times faster. –  Jonas Kibelbek Nov 5 '10 at 2:08
Yes, I acknowledge in the first line of my answer that this approach is the right one for small numbers like 2000. –  Charles Nov 5 '10 at 2:41

Sieving, alone, is a poor approach to the problem unless n is small (which, in your example, it is). A better approach for large numbers: choose an appropriate interval,* sieve out small primes, test remaining numbers with a probable-prime test, then (if desired) prove primality with ECPP or a similar algorithm (for small primes, APR-CL is better).

Many programs can do this search for you, though they generally omit the last step (Pari and Mathematica at least).

.* If the interval is chosen at random, length 4.5 log x is 95% likely to hold at least one prime, since $4.5e^{-4.5}\approx0.05$. If your interval is adversarially chosen to have few primes, you could choose an interval as long as about $2e^{-\gamma}\log^2x$. If performance is critical you can determine the optimal sieving distance based on time and other resources taken for both parts.

-
Thanks for the info (here and in response to my answer) about prime gaps! For anyone who doesn't have any mathematics software, you can use www.wolframalpha.com to search for the next (probable?) prime, using "NextPrime[N]". It can handle "NextPrime[10^1250]-10^1250" if you give it some extra time! –  Jonas Kibelbek Nov 5 '10 at 2:16
@Jonas Kibelbek: Pari/GP can also do that: nextprime(10^1250)-10^1250 takes less than 2 seconds. –  Charles Nov 5 '10 at 4:03

If you want to find several primes at once starting from some point, you can use a sieve.

-
+1, Sieving is the easiest and a fast way to compute this :) –  Quixotic Nov 4 '10 at 9:40

An integer $p$ is prime if and only if the following equation holds: \begin{eqnarray} \sum_{n \geq 1} \left \lfloor \frac{p}{n} \right \rfloor - \left \lfloor \frac{p-1}{n} \right \rfloor = 2 \end{eqnarray} NB: The infinite number of terms of sum is there to accommodate an arbitrarily large integer $p$, but the sum eventually produces a string of $0$s. (See Crandall and Pomerance, Prime Numbers: A Computational Perspective, New York: Springer, ISBN 0-387-04777-9)

After observing that $2001$ and $2002$ both violate the test early on but $2003$ does not, then you can use any number of primality tests (or choose to prove the sum equals 2 to establish primality directly). Otherwise, you may try something like Wilson's theorem, which states: An integer $p$ is prime if and only if $(p-1)! \equiv -1 \mod p$.

Mathematica gives the correct result in less than 1 second: $2003$ is the first prime greater than $2000$.

-
In practice, of course, one uses a probabilistic compositeness test like Miller-Rabin instead of Wilson or that other equation; most certainly if one is searching for huge primes. –  Ｊ. Ｍ. Nov 4 '10 at 7:13
For those curious on how it's done in Mathematica: Prime[PrimePi[2000] + 1] –  Ｊ. Ｍ. Nov 4 '10 at 7:29
I think NextPrime[2000] is simpler. –  user02138 Nov 4 '10 at 7:35
Right. :) For the ones who don't have newer versions of Mathematica, one either has to load the package NumberTheoryNumberTheoryFunctions to use NextPrime[] or use the construct I gave. –  Ｊ. Ｍ. Nov 4 '10 at 11:18
@J.M.: Fair point ;) –  user02138 Nov 4 '10 at 17:31
All prime numbers, except for $2$ and $3$, are of the form $6n\pm1$. Now, what's the nearest multiple of $6$ to $2000$ ? It can't be $2000$ itself, since, despite being even, the sum of its digits is not a multiple of $3$. The same holds for $2002$ as well. Then $2004$ is the answer. Let's check $2004-1=2003$. Indeed, it's prime.