sieve_size :: 1000000;
alloc_size :: #run: sieve_size / 8;
root :: #run: heron(sieve_size, 20);
bitset := scratch_allocate_t{u8}(alloc_size);
memset_bytes(bitset, alloc_size, u8_2b_1111_1111);
current_prime := 3;
while: current_prime < root
{
temp := current_prime;
while: temp < sieve_size
{
if: get_bit(bitset, temp)
{
current_prime = temp;
#break();
}
temp +=2;
}
double_prime := current_prime * 2;
index := current_prime * current_prime;
while: index < sieve_size
{
set_bit(bitset, index, false);
index += double_prime;
}
current_prime += 2;
}
heron :: #expand: (n: s32, rounds: s32) -> s32
{
guess := n/2;
i := 0;
while: i != rounds
{
guess = ( guess + (n/guess) ) / 2;
## the guess must be an overestimate. rounding errors can mess this up
if: guess * guess < n
{
++guess;
}
++i;
}
return guess;
};
get_bit :: #expand: (bitset: *u8, index: s32) -> bool
{
byte := index / 8;
mask := #cast(u8, 1 << (index % 8) );
return (bitset @ byte & mask) != 0;
};
set_bit :: #expand: (bitset: *u8, index: s32, val: bool)
{
byte := index / 8;
mask := #cast(u8, 1 << (index % 8) );
selected_byte := bitset @ byte;
selected_byte &= ~mask;
selected_byte ^= mask * #cast(u1, val);
bitset @ byte = selected_byte;
};