Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Next prime algorithm

Reply
Thread Tools

Next prime algorithm

 
 
ckroom
Guest
Posts: n/a
 
      06-13-2004
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

 
Reply With Quote
 
 
 
 
Kai-Uwe Bux
Guest
Posts: n/a
 
      06-13-2004
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
 
Reply With Quote
 
 
 
 
Dan
Guest
Posts: n/a
 
      06-14-2004

"Kai-Uwe Bux" <(E-Mail Removed)> wrote in message
news:cai7n1$a82$(E-Mail Removed)...
> 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



 
Reply With Quote
 
Dave Townsend
Guest
Posts: n/a
 
      06-14-2004

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
>



 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Algorithm for generating pitch-class sets in prime form John O'Hagan Python 1 02-10-2011 09:12 AM
Prime number algorithm in C Cmorriskuerten C Programming 33 07-22-2009 11:08 AM
CurrentElement->next = CurrentElement->next->next (UNDEFINED?) Deniz Bahar C Programming 2 03-09-2005 12:45 AM
Prime numbers: addative property modulo p, where p is prime Jeremy Fischer Perl Misc 0 01-16-2005 05:53 PM
Next prime algorithm ckroom C Programming 6 06-14-2004 05:15 PM



Advertisments