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
I wrote a short program in assembler, using Turbo Macro Pro, to implement a Sieve of Eratosthenes to find the 8 bit prime numbers.
Right click here to download the disk image: tmpsieve
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
head = $0890 ; header
; this is the header
; 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
adc w1
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
adc w2 ; add the step
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
printheader
ldx #$00
phloop
lda head,x
jsr chrout
inx
cpx #$44
bne phloop
rts
main
jsr dosieve
jsr printheader
;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
Paul's Notebook 