Double factorial and primorial
bodrato at mail.dm.unipi.it
bodrato at mail.dm.unipi.it
Wed Dec 21 16:11:13 CET 2011
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/
More information about the gmp-devel
mailing list