Sujet : Re: OT: Re: Sieve of Erastosthenes optimized to the max
De : vir.campestris (at) *nospam* invalid.invalid (Vir Campestris)
Groupes : comp.lang.c++Date : 20. Aug 2024, 22:14:30
Autres entêtes
Organisation : A noiseless patient Spider
Message-ID : <va2tf8$3gpbu$1@dont-email.me>
References : 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
User-Agent : Mozilla Thunderbird
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