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?
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.
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.
If you want to find several primes at once starting from some point, you can use a sieve.
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.
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$.
Prime[PrimePi[2000] + 1]
– J. M. ain't a mathematician
Nov 04 '10 at 07:29
NextPrime[] or use the construct I gave.
– J. M. ain't a mathematician
Nov 04 '10 at 11:18