Double factorial and primorial

Torbjorn Granlund tg at
Wed Dec 21 16:40:50 CET 2011

Torbjorn Granlund <tg at> writes:

A corrected version:
    for i = 0 ... Pi(2*S)-1
       p = primevec[i].p
       s = primevec[i].off
       while s < S
          sieve[s] = 1;
       primevec[i].off = s - 2*S
    while true
       <p,off> = pop(heap)
       if (off >= s0 + 2*S)
       sieve[off - s0] = 1;
       off = off + p
       insert(heap, <p,off>)

The variable s0 represents the number corresponding to sieve[0].
Outside of this resieve code, s0 is updated: s0 = s0 + 2*S.

The heap is initialised with <p,p^2> for 2*S < p <= sqrt(N) for the
planned limit N.  (It might be impractical to have a predetermined limit
N, in which case one needs to extend it as soon as s0+2*S-1 >= q^2 if q
is the largest prime currently in the heap.)


More information about the gmp-devel mailing list