Path: csiph.com!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: Sun, 18 Aug 2024 19:52:00 -0700
Organization: A noiseless patient Spider
Lines: 33
Message-ID: <86ttfhcjhr.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <utq0ag$hvrl$3@dont-email.me> <utq0os$ibqn$1@raubtier-asyl.eternal-september.org> <utq11p$icmm$1@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 19 Aug 2024 04:52:00 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="8e0243d997a628e731b4ff9e397b6328"; logging-data="2863641"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19aNamxqFISr7uAvrA5PdTfz0+hlk1lx5c="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:xJ25kgpV33jbWvqbLUQfiDaJDOg= sha1:NkolWghRElBvNcTcJmRFn3YkkQA=
Xref: csiph.com comp.lang.c++:119820

Tim Rentsch <tr.17687@z991.linuxsc.com> writes:

> Vir Campestris <vir.campestris@invalid.invalid> writes:
>
[...]

>> You seem to have spotted a pattern in the steps that I didn't - I
>> looked at the mask values, and decided it wasn't worth working out
>> which of the 8 possible sequences to use - remembering which was
>> too expensive.  But it's also (I think, I haven't coded it) to work
>> out whether you need to step 2, 4, 8 times the prime.  And that
>> would save more memory.
>
> The possible steps for mod30 are 2 or 4 or 6 times the prime.
>
>> Another thought BTW - whether it's worth storing with a larger
>> modulo - say 2*3*5*7 - not just 2*3*5 is a different decision from
>> deciding whether the steps between primes should take that into
>> consideration.
>
> My guess is that the possible steps are still just 2 or 4 or 6
> (times the prime), but I haven't checked that.

I guessed wrong.  Considered mod 210, there are

   15 steps of  2
   15 steps of  4
   14 steps of  6
    2 steps of  8
    2 steps of 10

(for a total of 48 residues) due to knocking out multiples of 7.