Croc

module samples.sieve

function main()
{
	local N = 1_000_000
	local start = time.microTime()
	local bits = array.new(math.iceil(N / ((math.intSize * 8) as float)), -1)

	// set 0 and 1 to false
	bits[0] &= ~3

	for(i; 2 .. math.sqrt(N) as int)
	{
		if(bits[i >> 6] & (1 << (i & 63)))
		{
			for(j; i * i .. N, i)
				bits[j >> 6] &= ~(1 << (j & 63))
		}
	}

	local count = 0

	for(i; 0 .. #bits)
	{
		local x = bits[i] - ((bits[i] & 0xAAAAAAAAAAAAAAAA) >>> 1)
		x = (x & 0x3333333333333333) + ((x >>> 2) & 0x3333333333333333)
		x = (x + (x >>> 4)) & 0x0F0F0F0F0F0F0F0F
		count += (x * 0x0101010101010101) >>> 56
	}

	local end = time.microTime()
	writefln("Took {:.3} ms", (end - start) / 1000.0)
	writefln("There are {} primes below {}.", count, N)
}