BASIC Program for Finding Pseudoprimes

Here's a little Quick Basic program the generates all the pseudoprimes
less than 30000 in about 30 seconds.

      DEFLNG A-Z
      DIM bit(32)

      FOR nn = 3 TO 30000

      FOR d = 2 TO SQR(nn)
      IF (nn MOD d) = 0 GOTO 50
      NEXT d: GOTO 999
     
50    n = nn: i = 0
100   bit(i) = n MOD 2: n = (n - bit(i)) \ 2: i = i + 1
      IF n > 0 GOTO 100
      ib = i - 1

      r = 1
200   r = (r * r) MOD nn
      IF bit(ib) = 1 THEN r = (r * 2) MOD nn
      ib = ib - 1: IF ib >= 0 GOTO 200

      IF r = 2 THEN PRINT nn, r

999   NEXT nn