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
Paul's Notebook 