Next prime algorithm

[ckroom]

Does anyone know 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

[Christian Bau]

In article <2j************ @uni-berlin.de>, ckroom <ck****@hotmail .com>
wrote:

Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

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

Try if n+1 is a prime number. If it isn't then try n+2. And so on. And
so on. You know how to find out if a number is a prime, don't you?

[Malcolm]

"ckroom" <ck****@hotmail .com> wrote

Does anyone know a good algorithm to get the next prime of a
number n?

prime = nextprime( n );

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

Just because you are implementing your algorithm in C doesn't make it
topical here.

However you can first sieve the list for factors of small prime numbers,
then do many tests for primality using the "witness" method, but finally to
be 100% sure you need to do an exhaustive search up to the square root of
the number you are testing.

[Michael Mair]

Hi there,

Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

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

Not really on topic.
Apart from the other answers you got, there is yet another way.

If the maximum argument to nextprime is limited by a small enough
number, you can calculate all primes up to the successor of that maximum
argument, using e.g. the Sieve of Eratosthenes, and store them in
an efficient manner, say set bits, exclude multiples of small prime
numbers. Then, essentially, you only have to search in your list for the
next set bit. Some time ago, I came across

http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html

However, I only had a look at the explanations, not at the source.
The author assumes 8 bits per byte which may not be true on your
machine - nonetheless, the idea is nice enough.

BTW: If the maximum is too high, just write all the required primes
to a file and read them into an array (->density of primes within
natural numbers; use the theory to predict the position of n and
search for n from that position in your array).
HTH
Michael

[Dik T. Winter]

In article <ca**********@n ewsg3.svr.pol.c o.uk> "Malcolm" <ma*****@55bank .freeserve.co.u k> writes:

"ckroom" <ck****@hotmail .com> wrote

Does anyone know a good algorithm to get the next prime of a
number n?

.... Just because you are implementing your algorithm in C doesn't make it
topical here.

However you can first sieve the list for factors of small prime numbers,
then do many tests for primality using the "witness" method, but finally to
be 100% sure you need to do an exhaustive search up to the square root of
the number you are testing.

Wrong. But the reasons are very off-topic here. (Primality proving programs
have in general a running time much better than O(sqrt(n)).)
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[CBFalconer]

ckroom wrote:

Does anyone know a good algorithm to get the next prime of a
number n?

prime = nextprime( n );

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

You can look in the source to hashlib for one method. See my site
below, download section.

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Alan Balmer]

On Sun, 13 Jun 2004 20:11:39 +0200, ckroom <ck****@hotmail .com> wrote:

Does anyone know a good algorithm to get the next prime of a number n?

prime = nextprime( n );

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

In spite of all the answers you've got, I think your question is
ambiguous. What do you mean by "the next prime of a number n"? Do you
mean the smallest prime greater than n? Do you mean the next prime
factor of n?

In any case, it's off-topic here.

--
Al Balmer
Balmer Consulting
re************* ***********@att .net