Re: OT: Re: Sieve of Erastosthenes optimized to the max

On 20/08/2024 05:08, red floyd wrote:
>

So I'm a little late, but here's my effort to use the modulo
30 trick.
>
Using g++ 12.4.0, Cygwin under Windows 11 22631, Ryzen 5
5600x, 64GB RAM
>
g++ -O3 -std=c++17
5761455 primess less than 100 million in 0.182269s
50847534 primes less than 1 billion in 2.841167s
455052511 primes less than 10billion in 53.009133s

>
It's slow.
>
Looking quickly at the (remarkably small) code I see line 30:
>
return std::make_tuple(val / MOD_VALUE, masks[val % MOD_VALUE]);
>
That mod and div are being called for every single time you
mark a prime in the bitmap.