The least prime greater than 2000

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.