Double factorial and primorial

Niels Möller nisse at
Wed Dec 21 13:36:30 CET 2011

bodrato at writes:

> A range delimited by? two unsigned long?

I imagine this interface is for efficiently generating a large number of
small primes. For large primes, one would have to iterate over
mpz_nextprime. Are there any large savings from storing additional state
between calls to mpz_nextprime?

> And whenever the callback returns a non-zero, the loop is interrupted, so
> that one can stop when the needed prime is found.

Sounds reasonable. Do you know any case where it's going to be useful?

> If the loop can be interrupted, it is probably better to return the last
> used prime (or zero if there are none in the range).

The user already knows this and can store it if needed. There should of
course be a user supplied ctx pointer passed to the callback, something

  typedef int prime_callback_func (void *ctx, unsigned long prime);
  unsigned long
  mpz_prime_sieve (unsigned long start, unsigned long end,
  	           void *ctx, prime_callback_func *f);

> The prime counting function can have its own interface and its specialised
> code: with a bitwise sieve, popcount is faster than some kind of loop.

Sure. I thought the number of generated primes would be a reasonable
return value, and the case f == NULL can be handled specially if it
allows optimizations beyond the obvious one of never calling the
function. But these fine details aren't terribly important now.


Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.

More information about the gmp-devel mailing list