Double factorial and primorial

[Torbjorn Granlund]

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