Hi there,
Does anyone know a good algorithm to get the next prime of a number n?
prime = nextprime( n );
It's for some stuff about double rehashing, thanks.
Not really on topic.
Apart from the other answers you got, there is yet another way.
If the maximum argument to nextprime is limited by a small enough
number, you can calculate all primes up to the successor of that maximum
argument, using e.g. the Sieve of Eratosthenes, and store them in
an efficient manner, say set bits, exclude multiples of small prime
numbers. Then, essentially, you only have to search in your list for the
next set bit. Some time ago, I came across
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
However, I only had a look at the explanations, not at the source.
The author assumes 8 bits per byte which may not be true on your
machine - nonetheless, the idea is nice enough.
BTW: If the maximum is too high, just write all the required primes
to a file and read them into an array (->density of primes within
natural numbers; use the theory to predict the position of n and
search for n from that position in your array).
HTH
Michael
