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.

primetime

 

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s