Next prime algorithm

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

  1. ckroom

    ckroom Guest

    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
    #1
    1. Advertising

  2. ckroom

    Kai-Uwe Bux Guest

    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
    #2
    1. Advertising

  3. ckroom

    Dan Guest

    "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
    #3
  4. 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" <> 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
    #4
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Cmorriskuerten

    Prime number algorithm in C

    Cmorriskuerten, Nov 17, 2003, in forum: C Programming
    Replies:
    33
    Views:
    54,391
    NaomiD
    Jul 22, 2009
  2. ckroom

    Next prime algorithm

    ckroom, Jun 13, 2004, in forum: C Programming
    Replies:
    6
    Views:
    3,838
    Alan Balmer
    Jun 14, 2004
  3. Deniz Bahar
    Replies:
    2
    Views:
    468
    Andrey Tarasevich
    Mar 9, 2005
  4. John O'Hagan
    Replies:
    1
    Views:
    578
    John O'Hagan
    Feb 10, 2011
  5. Jeremy Fischer
    Replies:
    0
    Views:
    184
    Jeremy Fischer
    Jan 16, 2005
Loading...

Share This Page