' BCX 2.77 bitsieve routine
' Cino Hilliard
'set the bits of the bytes of an array to mask out multiples of odd prime numbers
'leaving 0 bit sequences to represent sequences of prime numbers.
const maxn = 200000001
const maxn8 = 8*maxn
dim t1,t2
set mask[8] = 1,2,4,8,16,32,64,128
dim j as long
dim k as long
dim l as long
dim index
dim n as long
dim bit
dim bitpos
dim ct
DIM a[maxn] as byte
t1 = clock()
l=0
for k = 3 to sqr(maxn8) step 2
incr l
for j = k+l to maxn8 step k
index = int(j/8) 'get index of the array
bitpos = 8 - mod(j,8) 'get bit position
if bitpos = 8 then 'adjust for bitpos 8
decr index
bitpos = 0
end if
a[index] = a[index] or mask[bitpos] 'replace a[index] with set bits
next j
next k
t2 = clock()
print "took ";(t2-t1)/1000.0;" sec to index"
do
input "number ",n
l = 1
ct = 1
print 2;
for j = 0 to n/16
for k = 7 to 0 step-1 'get bits of the array index
l += 2
bit = a[j] and mask[k]
if not bit then
print l;
incr ct
end if
next k
next j
print
print "index ";index
print "primes < ";n;" = ";ct
until n = 0