Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c++
Subject: Re: OT: Re: Sieve of Erastosthenes optimized to the max
Date: Mon, 26 Aug 2024 10:59:33 -0700
Organization: A noiseless patient Spider
Lines: 37
Message-ID: <86zfoz412y.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <v25c87$1ld9m$1@dont-email.me> <86r0duwqgg.fsf@linuxsc.com> <v39o3l$1lvju$1@dont-email.me> <86o78mpnlf.fsf@linuxsc.com> <v3fv2u$2ursd$1@dont-email.me> <86ttibod7n.fsf@linuxsc.com> <86h6eaoi2r.fsf@linuxsc.com> <v4sool$1grge$1@dont-email.me> <867celixcw.fsf@linuxsc.com> <v5sg9s$mat4$1@dont-email.me> <86zfr0b9hw.fsf@linuxsc.com> <v638ud$25623$1@dont-email.me> <861q3o5do1.fsf@linuxsc.com> <v7tdts$29195$1@dont-email.me> <868qx45v5g.fsf@linuxsc.com> <v9lbns$11alj$1@dont-email.me> <86r0aojx1m.fsf@linuxsc.com> <v9o2kf$1gqv1$1@raubtier-asyl.eternal-september.org> <va88m0$ikl3$2@dont-email.me> <va8jfa$k5pk$1@redfloyd.dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 26 Aug 2024 19:59:37 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="d6baed66fa18aad174400126e3461865";
	logging-data="2699528"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1++MYRA0lHpdWkplYHpE2c6fb+Fg0vRtKs="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:oq3Y5LqkDTysH8p3lb54ACQelJw=
	sha1:QqnlbHfGWq5WUYB0oBamAJApbR0=
Bytes: 2954

red floyd <no.spam.here@its.invalid> writes:

> On 8/22/2024 1:56 PM, Vir Campestris wrote:
>
>> On 16/08/2024 18:35, Bonita Montero wrote:
>>
>>> But basically I don't think it is a good idea to skip numbers exept
>>> multiples of two.  With the three you save a sixth of memory, with
>>> the five you save a 15-th and at the end you get about 20% less
>>> storage (1 / (2 * 3) + 1 / (2 * 3 * 5) + 1 / (2 * 3 * 5 * 7) ...)
>>> for a lot of computation.  That's the point where I dropped this
>>> idea and I think this extra computation is higher than the time
>>> for the saved memory loads.
>>
>> I've been running some experiments.
>>
>> Skipping evens only is nice and simple on computation;  that's good.
>>
>> Skipping something else requires table lookups.  I've knocked up some
>> code that uses the correct table for skipping primes (but not for
>> mask bit selection) and run it for 2*3*5, 2*3*5*7, and 2*3*5*7*11.
>
> You can skip multiples of three, by starting with 7, and then
> alternately adding 4 then 2.
>
> e.g.
>
> incr = 2;
> for (val = 7 ; val < MAX_PRIME_TO_CHECK ; val += incr)
> {
>     check_for_prime(val);
>     incr = 6 - incr;
> }

As a matter of style I would normally fold the initialization and
update of 'incr' into the first and third expressions of the for()
loop control.