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.
Andy