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

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.