TPAL = TP Assembly Language

         Routine for Computing Primes
        ==============================
Routine PRIMES computes primes up to n by the sieve of Erathostenes,
complemented as explained on TP-book page 226. The routine is
completely self-contained, "PRIMEND:" labels its final line.

Inputs:  [A]= n < &/2,  p1,p2,p3,p4 stacky;
Returns: 2,3,5,... primes -= n  wordwise on T1,
         p1 on top word = pi(n),  p2,p3,p4 as before.

P.PRIMES: JPHA.ALARM,           if  n += &/2
        LC=2, CT1+, LM=3, MT1+, store 2,3
        LB=5, JNL.PRIM3,        if  n += 5  then main routine
        SB.C, JAZ.PRIM1,        if  n=2
        JHAZ.PRIM2,             if  n=3 or n=4
        P1-, CM,                for n=1 or n=0
PRIM1:  P1-, CM,                for n<3
PRIM2:  CT1, RTS,               store pi(n) and return
-------------------------------------------------------
Main part of PRIMES:  (for n += 5)
--------------------
        ADR .p.dp.n
PRIM3:  BT0+, LM=4, MT0+,       p:= 5,  dp:= 4
        AT0+, LC=0,             store n,  s:= 0
PRIM4:  CT0,                    save  s = number of sequences  on T0
        LCBM p, ML, LA.M,        p -> C,  v:= p^2 -> A  ([E]=0 by ML)
        LM.C, SM H1,            2p -> M
        LB n, JGR.PMERGE,       if  p^2 > n  then start merging
storing sequence of multiples  v = m.p  for m congruent 1, 5 mod 6,
        ZT1+,                   set bottom zero for sequence
        LK dp, KM, JKM.PRIM6,   if dp > 2 (then old dp equal to 4)
PRIM5:  AT1+, AD.M, AD.M,       v:= v + 4p
        JGR.PRIM7,              if  v > n  then exit
PRIM6:  AT1+, AD.M, JNG.PRIM5,  v:= v + 2p,  loop while  v -= n

next prime p:
-------------
PRIM7:  LA=6, SB dp, AT dp,     dp:= 6 - dp
        AD.C, LC.A,             p:= p + dp
        LB=1, LK=2,             t:= 1, dt:= 2
      : LA=6, SB.K, LK.A,       dt:= 6 - dt
        AD.B, LB.A, LA=0,       t:= t + dt
        LM.C, DIV, JAZ.PRIM7,   p = q.t + r,  if r=0 then next p
              LA.M, JGR,        trial divisions while q > t
        CT p, PTN 121,          store prime p and alternate T1/T2
        LC0, CP, J.PRIM4,       s:= s+1, loop for next sequence
        -----------------
Merging the sequences, increasing from bottom zero word on T1,T2,
---------------------  decreasing from top word &-1 on T3,T4;
PMERGE: AC.A, AT3, LM0,         set initial &-1 and get s
        JMZ.PRIM8,              if s=0 (for n<25)
                                       then empty final sequence
-PMERG- Pass for merging the sequences from T1,T2 upon T3,T4:
-------
PMRG1:  P1-, P2-, LAE.M,        parity(s) -> E
        SML 1, SB.M, LCM.A,     s:= ceil(s/2) -> M,C
        JEZ.PMRG2,              if old s was even
        PTN 121,                else adjust order of tapes
        AC.A, J.PMRG6,          and copy one sequence upon T3
        ---------------
PMRG2:  AC.A, LB2-,             init merge loop
        - - - - - -
PMRG3:  AT3+,                   here [A] first
PMRG4:  LA1-, JA.PMRG5,         loop while nonzero
      : BT3+, LB2-, JB,         copy remaining elements from T2
        J.PMRG7
        ----------
PMRG5:  JGR.PMRG3,              if [A] first
        JEQ.PMRG4,              if equal then skip [A]
        BT3+, LB2-, JB,         here [B] first; loop while nonzero
        - - - - - - - -
PMRG6:  AT3+, LA1-, JA,         copy remaining elements from T1
        - - - - - - - -
PMRG7:  DP1-A, DP2-A,           discard old sequences, here [A]=0
        PT 343, JCM.PMRG2,      loop for s sequences

-QMERG- Pass for merging the sequences from T3,T4 upon T1,T2:
-------
        P1+, P2+, P3-, P4-
        LABE.M, SBL 1,          parity(s) -> E,  floor(s/2) -> B
        SB.B, LCM.A,            s:= ceiling(s/2) -> M,C
        JE.QMRGE,               if old s was odd
QMRG2:  LA=0, LB4-,             init merge loop
        - - - - - -
QMRG3:  AT1+,                   here [A] first
QMRG4:  LA3-, JHAZ.QMRG5,       loop while below &-1
      : BT1+, LB4-, JHBZ,       copy remaining elements from T4
        J.QMRG7
        -----------
QMRG5:  JLS.QMRG3,              if [A] first
        JEQ.QMRG4,              if equal then skip [A]
        BT1+, LB4-, JHBZ,       here [B] first; loop while below &-1
        - - - - - - - - -
QMRG6:  AT1+, LA3-, JHAZ,       copy remaining elements from T3
        - - - - - - - - -
QMRG7:  LA=0, DP3-A, DP4-A,     discard old sequences
        PT 121, JCM.QMRG2,      loop for s sequences
        P3+, P4+, J.PMRG1,
        -------------------
QMRGE:  PT 343,                 adjust order of tapes (since old s odd)
        LA=0, JB.QMRG6,         and copy one sequence upon T1, if old s > 1
        P4+,                    else adjust p4 and enter finals

Final part of PRIMES:
---------------------
PRIM8:  LA=5, LCMK=2,           p:= 5,  pi:= 2,  h:= 0 -> HM
PRIM9:  AT1+, CP,               store prime and count  pi:= pi + 1
PRIMA:  AD.K, HM+,              p:= p+2, h:= not(h)
        JHM.PRIMB,  AD.K,       p:= p+2, if h=0
PRIMB:  LB3-, JEQ.PRIMA,        no prime, if p is an element of the sequence
        P3+, LB n, JNG.PRIM9,   while  p -= n
        LA=0, DP3-A,            discard merge sequence
PRIMEND:P0-3, CT1, RTS,         store pi(n) and return
-------------------------------------------------------------------------
END.