Double factorial and primorial

[bodrato at mail.dm.unipi.it]

Il Mer, 21 Dicembre 2011 1:36 pm, Niels Möller ha scritto:
> bodrato at mail.dm.unipi.it writes:

> 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?

Probably not, you are right.

>> 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?

Trial division in primality testing.
Anyway one may be looking for a prime with a given property, e.g.:
 - find a prime p in [a,b] s.t. (p^d-1)/(p-1) is (pseudo-)prime,
 - find the biggest primorial p# < 2^a .

>   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);

Reasonable, and not difficult to implement.

>> The prime counting function can have its own interface and its

> 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

You are right. The number of generated primes is a reasonable information
to return, it makes sense even if the loop is interrupted, to count the
used primes.

Regards,
Marco

-- 
http://bodrato.it/papers/