# Double factorial and primorial

Torbjorn Granlund tg at gmplib.org
Wed Dec 21 16:29:39 CET 2011

```nisse at lysator.liu.se (Niels Möller) writes:

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.

It is certainly possible to handle all primes, also those < 2*S
with the heap.

I am suggesting this structure

for i = 0 ... Pi(2*S)
p = primevec[i].p
s = primevec[i].off
while s < S
sieve[s] = 1;
primevec[p].off = s - 2*S

while true
p,off = pop(heap)
if (off >= s0 + 2*S)
break
sieve[off - s0] = 1;

I.e., two non-nested loops.  By deparating primes into those < 2*S and
thos larger, the 2nd loop above will not need any inner loop.

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

I meant 19 bits for the primes, 45 bits for the offsets.  But it should
be better to use 1/3 of the bits for the primes, 2/3 for the offsets.
The "heap key" to use is the offsets.  64 bits should suffice for
prime+offset.

--
Torbjörn
```