; Sieve of Erastosthenes

; Demo program for ATALAN programming language

;(c) 2010 Rudla Kudla

;

;This version uses bit array so it can find primes up to $ffff.


use atari
out rtclock1@20:byte
out rtclock2@19:byte

;Maximum possible prime number.


const max_prime = $ffff

const	bmax = max_prime/8
count:0..max_prime

const
	mask:array(0..7) = 1,2,4,8,16,32,64,128
	maskx:array(0..7) = %1111'1110,%1111'1101,%1111'1011,%1111'0111,%1110'1111,%1101'1111,%1011'1111,%0111'1111
	
flags:array(bmax)

rtclock1 = 0
rtclock2 = 0

for i:0..bmax flags(i)=$aa

for i:3..sqrt max_prime step 2 where (flags(i/8) bitand mask(i mod 8) <> 0)
	for k:i*i..max_prime step 2*i
		flags(k/8) = flags(k/8) bitand maskx(k mod 8)

count = 1
for k:3..max_prime step 2 where (flags(k/8) bitand mask(k mod 8) <> 0) 
	inc count

t = rtclock2 * 256 + rtclock1
	
"[count] prime numbers in[t] ticks"