8190 CONSTANT SIZE
create FLAGS   SIZE ALLOT

sieve-version 1 = [if]
    \ Gilbreath sieve
    \ taken from https://home.hccnet.nl/a.w.m.van.der.horst/sieve.frt
    \ original in Byte Jan 1983

\ : DO-PRIME
: primes ( -- n )
FLAGS SIZE 1 FILL ( SET ARRAY )
0 ( 0 COUNT ) SIZE 0
DO FLAGS I + C@
    IF I DUP + 3 + DUP I +
        BEGIN DUP SIZE <
        WHILE 0   OVER FLAGS +   C!   OVER + REPEAT
        DROP DROP 1+
     THEN
LOOP
\ . ." PRIMES" ;
;
[then]

sieve-version 2 = [if]
\ gforth's siev.fs (uses address arithmetic and DO for the inner loop)
variable eflag flags size + eflag !
\ FLAGS 8190 + CONSTANT EFLAG

: PRIMES  ( -- n )  FLAGS 8190 1 FILL  0 3  EFLAG @ FLAGS
  DO   I C@
       IF  DUP I + DUP EFLAG @ <
           IF    EFLAG @ SWAP
                 DO  0 I C! DUP  +LOOP
           ELSE  DROP  THEN  SWAP 1+ SWAP
           THEN  2 +
       LOOP  DROP ;
[then]    

sieve-version 3 = [if]
\ variation of 2, uses u+do, a constant EFLAG, and uses SIZE
    flags size + constant eflag
    : primes  ( -- n )
	flags size 1 fill
	0 3 eflag flags do
	    i c@ if
		eflag over i + u+do
		    0 i c!
		dup +loop
		swap 1+ swap then
	    2 + loop
	drop ;
[then]

sieve-version 4 = [if]
    \ based on 3; limits the outer loop to end at sqrt(max), counts
    \ separately
    flags size + constant eflag
    flags 63 + constant sieve-limit
    : primes  ( -- n )
	flags size 1 fill
	3 sieve-limit flags do
	    i c@ if
		eflag over i + u+do
		    0 i c!
		dup +loop
	    then
	    2 + loop
	drop
	0 eflag flags do
	    i c@ + loop	;
[then]

sieve-version 5 = [if]
    \ based on 4; lower bound of inner loop is p^2
    flags size + constant eflag
    flags 63 + constant sieve-limit
    : primes  ( -- n )
	flags size 1 fill
	3 3 sieve-limit flags do ( m [m^2-m]/2 )
	    i c@ if
		eflag over i + u+do
		    0 i c!
		over +loop
	    then
	    over 2* + 1+ swap 2 + swap
	loop
	2drop
	0 eflag flags do
	    i c@ + loop	;
[then]


sieve-version 6 = [if]
    \ based on 5; outer loop limit like 3
    flags size + constant eflag
    flags 63 + constant sieve-limit
    : primes  ( -- n )
	flags size 1 fill
	3 3 eflag flags do ( m [m^2-m]/2 )
	    i c@ if
		eflag over i + u+do
		    0 i c!
		over +loop
	    then
	    over 2* + 1+ swap 2 + swap
	loop
	2drop
	0 eflag flags do
	    i c@ + loop	;
[then]


sieve-version 7 = [if]
    \ based on 5; keep address of first flag to erase around
    flags size + constant eflag
    flags 63 + constant sieve-limit
    : primes  ( -- n )
	flags size 1 fill
	3 flags 3 + sieve-limit flags do ( m flags+[m^2-3]/2 )
	    i c@ if
		eflag over u+do
		    0 i c!
		over +loop
	    then
	    2 under+ over 1- 2* +
	loop
	2drop
	0 eflag flags do
	    i c@ + loop	;
[then]


sieve-version 8 = [if]
    \ based on 7; outer loop over start addresses of first flag to erase
    flags size + constant eflag
    : primes  ( -- n )
	flags size 1 fill
	flags 3 eflag flags 3 + do ( addr m )
	    over c@ if
		eflag i u+do
		    0 i c!
		dup +loop
	    then
	    1 under+ 2 +
	    dup 1- 2* +loop
	2drop
	0 eflag flags do
	    i c@ + loop	;
[then]


: run-bench 0 10000 0 do primes nip loop ;