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: Sieve of Erastosthenes optimized to the max
Date: Tue, 21 May 2024 19:06:07 -0700
Organization: A noiseless patient Spider
Lines: 23
Message-ID: <86r0duwqgg.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <um2dsb$17vgg$2@dont-email.me> <um2vpr$1e7pn$1@raubtier-asyl.eternal-september.org> <um31o0$1edq3$1@dont-email.me> <um4f1l$1l1c2$1@raubtier-asyl.eternal-september.org> <um7haa$274oh$3@dont-email.me> <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>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Wed, 22 May 2024 04:06:09 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="ef527a1f0ace8b0bcb46bd1e68f4f6ae";
	logging-data="1042967"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/OVfKCw9pLdZWtJ8A2c5h5tu8VizIRbU4="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:1sqEPJFI8gZU/OWVOL/nO6zybjI=
	sha1:8S64xP4DIV0CPcGhbdUsQoGm/c8=
Bytes: 2771

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

> I've been playing with this.  Has it really been this long?  I
> ought to have more time than this...  [...]
>
> I missed Tim's Mod 30 trick, and that might well help.  But I
> think I'm bored with this.  It would save a lot of memory, but
> the extra computation might make it slower.

Two comments.  Using the mod 30 encoding can be speed competitive
with simpler encodings.  The second comment is, it isn't just
that less memory is used, but that more primes can be found.
Bonita brags about how fast some code is, but it's an apples
and oranges comparison - that code doesn't do the job because
it runs into a memory limit way sooner than using a mod 30
encoding, and trying to run past that limit would make the
code R E A L L Y  S L O W.

> Maybe I'll try one day ;)

I hope you do.  If you have some difficulty seeing how to
avoid the seeming speed penalties, feel free to ask, I am
happy to help.