No such thing as a small change  
PerlMonks 
Comment on 
( #3333=superdoc: print w/ replies, xml )  Need Help?? 
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 x1 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. In reply to Re^5: a close prime number
by dragonchild

