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

"ckroom" <(E-Mail Removed)> wrote in message

news:(E-Mail Removed)...

> 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.

>

> --

> ckroom

> http://nazaries.net/~ckroom

>