Re: Next prime algorithm
From: Dave Townsend (datownsend_at_comcast.net)
Date: 06/14/04
- Next message: Pete C.: "Re: accessing args via command line"
- Previous message: mark: "accessing args via command line"
- In reply to: ckroom: "Next prime algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 13 Jun 2004 19:33:27 -0700
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" <ckroom@hotmail.com> wrote in message
news:2j3cg7Ft1inuU1@uni-berlin.de...
> 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
>
- Next message: Pete C.: "Re: accessing args via command line"
- Previous message: mark: "accessing args via command line"
- In reply to: ckroom: "Next prime algorithm"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
