Double factorial and primorial

[Niels Möller]

Torbjorn Granlund <tg at gmplib.org> writes:

> For primes < 2*S, we sieve as usually, i.e., good old Eratosthenes.  For
> primes > 2*S we insert the squares in a minheap.

One could do a kind of unified way. Use a current block (bitmap). Get
the smallest element from the heap (p and a multiple of p), mark it in
thee bitmap, and continue to mark larger multiples (like good old
Erathostenes). When you get a multiple beyond the end of the current
block, put that back into the heap.

> Representation is not clear.  Perhaps 19 bits for the heap keys, that
> would alloow for the remaining 45 bits to be used by the prime.

I'm not sure what you mean by heap key. As far as I understand, the
primary elements in the heap (used for the sorting) would be multiples
of the primes, and I doubt these will fit in 19 bits). And then for each
multiple, we also need to know what the prime is. I imagine it would be
well sufficient with two arrays, one with 64-bit elements for the
multiples (the heap), and one with 32-bit array used for indexing the
list of primes (swapped together with the heap elements), but there's
room for more cleverness.

Ah, and one more question. When marking multiples of p, we don't need to
mark multiples where we know that p can't be the smallest prime factor.
This means that there's no need to mark the multiples between (3p, ...
(p-2) p. That's why the first multiple we need to mark is p^2. Can this
be generalized? Above p^2, it should be sufficient to mark multiples p
p', where p' are the primes larger than p.

So if we can delay the marking of p multiples >= p^2 until we have generated
all primes < p^2, we can use this list to mark p multiples in the range
[p^2, p^3]. Is this worthwhile? Maybe it is the same O(n/log log n)
sieving algorithm which Marco mentioned?

Regards,
/Niels

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