Next prime algorithm

C

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

Christian Bau

ckroom <[email protected]> said:
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?
 
M

Malcolm

ckroom said:
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.
 
M

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
 
D

Dik T. Winter

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

CBFalconer

ckroom said:
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.
 
A

Alan Balmer

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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Any Ideas On This Simple Co-Prime program 1
Next prime algorithm 3
Function for primes 0
Complex Python challenge 1 3
Langton's Ant 0
Beginners prime number generator 10
Java 1
Q for a source code in an exercise 1

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,904
Latest member
HealthyVisionsCBDPrice

Latest Threads

Top