Next prime algorithm

[ckroom]

Anyone knows a good algorithm to get the next prime of a number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.

 

[Kai-Uwe Bux]

Anyone knows a good algorithm to get the next prime of a number n?

prime = nextprime( n );

It's for some stuff about double rehashing, thanks.

First, this is not about C++, is it?

But anyway: I assume, by nextprime(n) you mean the smallest prime number
not less than n? If the argument n stays reasonably small, I would use a
binary search wihtin a precomputed array of all relevant primes to find the
least upper bound. Probably, one could optimize this a little by expoiting
the fact that there are on the order of n/ln(n) primes below n.

If n can be so big that a precomputed array is not an option, you will have
to go through many numbers and test them for primality. There are
reasonably fast probabilistic algorithms for doing that. Any decent book on
cryptography should give you some pointers.
However, even if you can test primality quickly, finding the next prime
will still be *very* costly. For hashing, you might want to look into
something else.


Best

Kai-Uwe

 

[Dan]

First, this is not about C++, is it?

But anyway: I assume, by nextprime(n) you mean the smallest prime number
not less than n? If the argument n stays reasonably small, I would use a
binary search wihtin a precomputed array of all relevant primes to find the
least upper bound. Probably, one could optimize this a little by expoiting
the fact that there are on the order of n/ln(n) primes below n.

If n can be so big that a precomputed array is not an option, you will have
to go through many numbers and test them for primality. There are
reasonably fast probabilistic algorithms for doing that. Any decent book on
cryptography should give you some pointers.
However, even if you can test primality quickly, finding the next prime
will still be *very* costly. For hashing, you might want to look into
something else.

This is a nice program with arrays, lots of maths, I remember doin g
something about finding the first 10 prime number, Just search on google
for what prime number is, its all math after that.

D

 

[Dave Townsend]

How big are your numbers ?

If you are dealing with simple 32 bit unsigned integers/longs, you could
do a simple "walk" from the given value for n, and test for n+1, n+2, etc
being prime by simply looking at the remainders for division by 2, 3, 5,7,
9,11,
etc. I tried this out, I can compute the next 1000 primes for n in the
1000,000,000
range in about 1 second, so its fairly quick.

If you can store primes <= sqrt(n) you can even eliminate many of the
operations
by modulus'ing only the primes, but for large n's there will probably be too
many
primes to keep track of. You could also pre-compute a table of primes and
store that.

Do you really want the "next" prime, since in some circumstances the next
prime is not
much bigger than the original, it might be more useful to jump to the next
prime which
is more than say, twice, the size of the original, so you can grow your hash
tables more quickly.
In that case, you could precompute all the primes satisfying this condition
ahead of time and
store them as constants in your algorithm code.

Does that help?

dave