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

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.