Hans L thehans at
Thu Sep 5 19:49:18 UTC 2019

What are the axes in the chart of your original post?

By the way, I wonder how commonly next_prime is used to generate a
large sequence of straight consecutive primes, in which case I think
it would be very beneficial to implement a segmented sieve that keeps
some state between calls, having the successive primes already sieved
and queued up after the first call etc.  Probably would make the most
sense a new/separate interface designed explicitly for that case.

Because a segmented sieve would be 1000's of times faster (for single
limbs sizes at least).  See the application "primesieve" ( ) for an example of a very
efficient sieve algorithm that works up to 2^64.
Even the simplified example implementation as part of primesieve's
docs is quite fast:
(eg. primes up to 1e9 in 0.65s)

As a rough comparison I ran mpz_nextprime consecutively up to 1e9 and
it took a total of 16m22.553s (on a Ryzen 2700x @4.0GHz).


On Tue, Sep 3, 2019 at 6:41 PM Seth Troisi <braintwo at> wrote:
> I think this small cleanup patch is appropriate given the testing of the
> other
> patch which I've tried several variations of and have been unable to improve
> beyond the existing implementation.
> The idea is to try and avoid performing modulo by storing the distance to
> the
> next multiple of each prime. This avoids divisions, unfortunately it
> requires
> writing back to the table each time a multiple is passed.
> I'm happy to look at other ideas but I think these comments can be cleaned
> up.
> _______________________________________________
> gmp-devel mailing list
> gmp-devel at

More information about the gmp-devel mailing list