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?
Best Answer
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.