Let me rephrase: There is no mathematical way to predict what the next prime number is, given any other number. In other words, there is no f(x) that will return the prime number closest to x without looking at either x-1 or x+1 first. (Unless, of course, either of those is a prime number.)

Furthermore, every single prime number generator is a variation on brute force. Your own nearest_prime() is a perfect example of this - you look at every number above and below n until you find one that is prime. That is a brute force algorithm.

As for primality tests, I refer you to Google's cache of the Wikipedia article (as it seems that en.wikipedia.com currently isn't available). Specifically, there are two quotes by some rather famous mathematicians. I'll repeat the one by Euler:

Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate.

If there is no order in the sequence of the primes, then there is no way to predict the closest prime to a given number. It is possible to determine it, but not to predict it.

Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.