Double factorial and primorial

[Niels Möller]

bodrato at mail.dm.unipi.it writes:

> An asymptotically faster sieve than Erathosteses' exists, but I do not
> know if it is worth implementing it; as it is O(N/loglogN) compared to
> O(N)...

I see. So Erathostenes it is, then.

> In fac_ui.c there already is a function for sieving: bitwise_primesieve.
> It fills an mp_ptr "with the characteristic function of composite"s, and
> it returns the count of "prime integers in the interval [4, n]".

That's going to use a lot more memory than necessary. To sieve all
primes up to n, you need to first create a list of primes up to sqrt(n),
and represent it in any convenient way which lets you iterate over it
(bitmap, or vector of differences, being the two most obvious choices).

Above sqrt(n), do the sieving blockwise. Create a bitmap of a suitable
blocksize (it should fit in the cache), let this bitmap represent some
interval, e.g., the first block would be [floor(sqrt(n)) + 1,
floor(sqrt(n)) + s]. Then iterate over the list of primes below sqrt(n)
to strike all composite numbers in the block. Then output anything you
need those primes for, and reuse the bitmap storage for the next
interval.

I think the trialdiv code currently in gmp also includes some sieve?

> counting the primes in [1,2^34] required half the time of
> (sieving and) multiplying all primes in [1,3*2^28].

So sieving is a significant part of the work for the primorial function.
I imagine you already arrange the multiplications so you get roughly
balanced operations?

Regards,
/Niels


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