Path: csiph.com!news.mixmin.net!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: Sieve of Erastosthenes optimized to the max
Date: Sun, 02 Jun 2024 19:50:36 -0700
Organization: A noiseless patient Spider
Lines: 24
Message-ID: <86h6eaoi2r.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <um8vlp$2h8oc$1@raubtier-asyl.eternal-september.org> <uma7i4$2nagg$1@dont-email.me> <umdmkf$3clht$1@raubtier-asyl.eternal-september.org> <umdovb$3cmi3$2@dont-email.me> <ume6ap$3ecjk$1@raubtier-asyl.eternal-september.org> <umfcqi$3jktj$2@dont-email.me> <umgbci$3qpao$1@raubtier-asyl.eternal-september.org> <utlf3h$393l6$1@dont-email.me> <utn1fp$3oeks$2@raubtier-asyl.eternal-september.org> <utng4n$3rn1f$2@dont-email.me> <utoh9d$6lrr$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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 03 Jun 2024 04:50:36 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="df68cad4d9500866e5e56f3de5ab6749"; logging-data="3920212"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/uNVWID3uL2tk45bVX9KfNd64gMDVzlo0="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:A9k8b60jsRVPqtAmdkBL3OPb7x0= sha1:lkGJZeC3mxEmJqEPPrTOrCkbWpI=
Xref: csiph.com comp.lang.c++:119457

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

> Pseudocode now looks something like this:
>
>     for each index i in the table :
>       for each bit in table[i] :
>         if that bit has been marked composite : continue
>         // we have found the next prime
>         for each index j > i in the table :
>           for each bit in table[j] :
>             if that bit has beem marked composite : continue
>             // we have found a multiplier m and ..
>             // need to mark as composite p*m
>           end
>         end
>       end
>     end

Correction:  that should be

        for each index j >= i in the table :

Also I have left out some possible optimizations, in the
interest of simplifying the explanation.