# Next prime algorithm

Discussion in 'C++' started by ckroom, Jun 13, 2004.

1. ### ckroomGuest

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

ckroom, Jun 13, 2004

2. ### Kai-Uwe BuxGuest

ckroom wrote:

> 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

Kai-Uwe Bux, Jun 13, 2004

3. ### DanGuest

"Kai-Uwe Bux" <> wrote in message
news:cai7n1\$a82\$...
> ckroom wrote:
>
> > 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.
>

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

Dan, Jun 14, 2004
4. ### Dave TownsendGuest

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
store them as constants in your algorithm code.

Does that help?

dave

"ckroom" <> wrote in message
news:...
> 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
>

Dave Townsend, Jun 14, 2004