## A comparison of using a Sieve of Eratosthenes vs. Trial Division to find primes on a C64 in BASIC

I wrote a BASIC program for the Commodore 64 to compare run times for finding primes using both a Sieve of Eratosthenes and Trial Division.

Here is the screen shot, with the sieve (clearly the winner) at the top, and the trial division run at the bottom.

Here is a disk image:  sievevstrial

Here is the code:

```5 print chr\$(147)
10 u=10
20 dim a%(2^u + 1)
25 m = int((2^u)/log(2^u))
30 dim b%(int(1.5 * m))
50 print "sieve"
60 print "====="
70 print "limit","primes","  time"
80 print "-----","------","  ----"
100 for n = 8 to u
105 t = time
110 lm = 2^n : sm = int(sqr(lm))
200 for i = 1 to lm : a%(i)=1 : next i
210 a%(1) = 0
500 for p = 2 to sm
520 if a%(p) = 0 then 620
560 for ct = 2*p to lm step p
580 a%(ct) = 0
600 next ct
620 next p
630 pc = 0
640 for i = 1 to lm
660 if a%(i) = 0 then 700
680 pc = pc + 1
700 next i
705 s = (time-t)/60
706 s = int(100*s)/100
500 for p = 2 to sm
520 if a%(p) = 0 then 620
560 for ct = 2*p to lm step p
580 a%(ct) = 0
600 next ct
620 next p
630 pc = 0
640 for i = 1 to lm
660 if a%(i) = 0 then 700
680 pc = pc + 1
700 next i
705 s = (time-t)/60
706 s = int(100*s)/100
710 print "2^";n,pc,s
720 next n
1000 print : print "Trial"
1010 print "====="
1020 print "limit","primes","  time"
1030 print "-----","------","  ----"
1040 for n = 8 to u
1042 lm = 2^n
1045 b%(1) = 2
1050 t = time
1060 pc = 1
1070 for x = 3 to lm
1080 for y = 1 to pc
1090 w = x/b%(y)
1095 if w = int(w) then 1200
1100 if (b%(y)*b%(y)) > x then goto 1120
1110 next y
1120 pc = pc + 1
1130 b%(pc) = x
1200 next x
1270 s = (time-t)/60
1275 s = int(100*s)/100
1300 print "2^";n,pc,s
1400 next n

```

## A Sieve of Eratosthenes in Assembler

I wrote a short program in assembler, using Turbo Macro Pro, to implement a Sieve of Eratosthenes to find the 8 bit prime numbers.

Here is the screenshot:

The ML program places a basic program in memory that is just:

10 SYS 4096

So, once SIEVE is loaded, (LOAD “SIEVE”,8,1), all one has to do is type RUN to run the sieve.

```chrout   = \$ffd2

sieve    = \$0900   ; 8 bit sieve

*= \$0800

;the 00 byte that starts basic

.byte \$00

; pointer to the next basic line
; which is at \$080c
.byte \$0c,\$08

; line 10
.byte \$0a,\$00

; the basic token for sys
.byte \$9e

; a space
.byte \$20

; "4096"
.byte \$34,\$30,\$39,\$36

; 00 for the end of the basic line
.byte \$00

; 00 00 for the end of the basic
; program
.byte \$00,\$00

w1       = \$0880; working variable
w2       = \$0881; working variable
w3       = \$0882; working variable
w4       = \$0883; working variable
w5       = \$0884; working variable
hx       = \$0885; holder for x
hy       = \$0886; holder for y
hdig     = \$0887; hundreds digit
tdig     = \$0888; tens digit
odig     = \$0889; ones digit

; it is 68 bytes

*= \$0890
;[clr][sp][sp][sp]
.byte \$93,\$20,\$20,\$20

;[sp][sp][sp][sp]
.byte \$20,\$20,\$20,\$20

;[sp]eig
.byte \$20,\$45,\$49,\$47

;ht[sp]b
.byte \$48,\$54,\$20,\$42

;it[sp]p
.byte \$49,\$54,\$20,\$50

;rime
.byte \$52,\$49,\$4d,\$45

;[sp]num
.byte \$20,\$4e,\$55,\$4d

;bers
.byte \$42,\$45,\$52,\$53

;[cr][sp][sp][sp]
.byte \$0d,\$20,\$20,\$20

;[sp][sp][sp][sp]
.byte \$20,\$20,\$20,\$20

;by[sp]a
.byte \$42,\$59,\$20,\$41

;[sp]sie
.byte \$20,\$53,\$49,\$45

;ve[sp]o
.byte \$56,\$45,\$20,\$4f

;f[sp]er
.byte \$46,\$20,\$45,\$52

;atos
.byte \$41,\$54,\$4f,\$53

;then
.byte \$54,\$48,\$45,\$4e

;es[cr][cr]
.byte \$45,\$53,\$0d,\$0d

*= \$1000

jmp main

mult10   ; multiply by 10 subroutine

asl a
sta w1
asl a
asl a
rts

; now, in order to output base-10
; values to the screen we need
; to get a char which represents
; each digit in the base-10
; representation of the 8-bit
; number to be output

; we will store the hundreds place
; digit in hdig, the tens plae
; digit in tdig, and the ones
; place digit in odig

; get hundreds digit subroutine

gethundig

cmp #\$c8  ; is a gt 200?
bcc hless200
ldx #\$02  ; if here, hdig is
stx hdig  ; 2 so store it
sec
sbc #\$c8  ; subtract 200 from
rts       ; a and return

hless200
cmp #\$64  ; is a gt 100?
bcc hless100
ldx #\$01  ; if here, hdig is
stx hdig  ; 1 so store it
sec
sbc #\$64  ; subtract 100 from
rts       ; a and return

hless100
ldx #\$00  ; if here, hdig is
stx hdig  ; 0 so store it
rts

gettendig
; when this sub is run, a is 0-99

; start by putting a 9 in x,
; multiplying that by 10, then
; seeing if 90 is higher than the
; test number - if not, tdig is 9,
; and so on

sta w2; preserve a
ldx #\$09

tryaten
txa
jsr mult10
sta w3; w3 = 90,80,70,etc

lda w2
cmp w3
bcc tennotfound
txa  ; we hav found our ten
sta tdig
lda w2
sec
sbc w3
rts  ; we've found the digit,
; and left the ones place
; in a - so return

tennotfound
dex  ; try the next lower
bne tryaten
ldy #\$00; if here, tdig=0
sty tdig
lda w2
rts

getonedig
sta odig; by this time, the
; ones digit is all that
; is left in a
rts

getdigs
jsr gethundig
jsr gettendig
jsr getonedig
rts

printdigs
jsr getdigs
lda hdig
ora #\$30; convert to ascii
jsr chrout
lda tdig
ora #\$30
jsr chrout
lda odig
ora #\$30
jsr chrout
lda #\$20; two spaces
jsr chrout
jsr chrout
rts

dosieve
ldx #\$00; use x to index loop1
lda #\$01
loop1
sta sieve,x; fill the sieve wit
inx
bne loop1

lda #\$00
ldx #\$00
sta sieve,x; 0 is not prime
inx
sta sieve,x; 1 is not prime

; w1 is counter as we step
; w2 is step size
lda #\$01
sta w1
sta w2

nextpass

inc w2; if we are on first pass
; through sieve, we just
; increased step from 1 to 2
; which is what we want

lda w2; the step size is also
; the first element in
; any pass
sta w1

cmp #\$10; have we reached 16?
; if so, we ar done
bne not16
rts

not16
ldx w2
lda sieve,x; does x point to a
; zero in the sieve?
beq nextpass ; ifso x composite
; so move on

nextstep

lda w1
txa
beq nextpass; we've stepped all
; the way through
; sieve so increase
; step

lda w1
bcs nextpass; if the carry flag
; is set we're past
; the end of the
; sieve so nextpass

sta w1
tax     ; update x pointer

lda #\$00
sta sieve,x; x not prime so
; mark with a zero
jmp nextstep

ldx #\$00
phloop
jsr chrout
inx
cpx #\$44
bne phloop
rts

main
jsr dosieve

;sieve now marks primes
;with a 1 - step and
;print primes

ldy #\$00
sty w5; w5 is primes on
; this current line

probesieve

lda sieve,y
beq movetonext
tya
stx hx
sty hy
jsr printdigs
ldy hy
ldx hx

inc w5
lda w5
cmp #\$08; end of line?
bne movetonext
lda #\$0d
jsr chrout
lda #\$00
sta w5; reset line index

movetonext
iny
bne probesieve
lda #\$0d
jsr chrout
jsr chrout
rts
```