Path: csiph.com!news.swapon.de!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: A better sieve (was Re: Sieve of Erastosthenes optimized to the max)
Date: Sat, 20 Apr 2024 08:35:23 -0700
Organization: A noiseless patient Spider
Lines: 26
Message-ID: <86wmosvyh0.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <un594t$3hn5o$1@raubtier-asyl.eternal-september.org> <unagvf$ft9g$1@dont-email.me> <unaus6$h9l0$1@raubtier-asyl.eternal-september.org> <20240106000249.177@kylheku.com> <unb6jc$i4of$1@raubtier-asyl.eternal-september.org> <uncfue$ojf6$1@dont-email.me> <undpp4$117ni$1@raubtier-asyl.eternal-september.org> <unf2ip$16tqc$1@dont-email.me> <ung2bt$1eihc$1@raubtier-asyl.eternal-september.org> <20240108175039.572@kylheku.com> <unjk7k$21eto$1@raubtier-asyl.eternal-september.org> <up95f1$kibc$1@dont-email.me> <86frxsz94r.fsf@linuxsc.com> <uqo64i$3usjj$1@raubtier-asyl.eternal-september.org> <86il2fwapd.fsf@linuxsc.com> <urcds6$14fvi$1@raubtier-asyl.eternal-september.org> <86wmqtszd0.fsf@linuxsc.com> <urfk4u$1tar2$1@raubtier-asyl.eternal-september.org> <86r0ggr8xb.fsf@linuxsc.com> <usp6fv$72id$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 20 Apr 2024 17:35:24 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9997d8b7c87f6a9dee0ccc592fd139d0"; logging-data="3936409"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/pEOlpoN1+E2S97KZAlfjah9F498y23pk="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:QajQ6jFFlGvpETLvimDmfbTWXcE= sha1:jq963DBlKip350uj341UZopaF3k=
Xref: csiph.com comp.lang.c++:118813

Bonita Montero <Bonita.Montero@gmail.com> writes:

> Am 11.03.2024 um 18:10 schrieb Tim Rentsch:
>
>> Sounds like you're using 1 bit per number, most of which are
>> wasted.  If you use a different encoding the memory requirements
>> can be much smaller.  How much memory do you have on the box?
>> If you have 64G you should be able to determine all primes
>> less than 1.5 trillion, using a simple encoding.
>
> I'm omitting even numbers and I handle the number two as a
> special case;  that's the fastest solution.
>
>> I've mentioned this encoding before but let me give it again.
>> If numbers are considered mod 30, there are only 8 residues
>> that are not divisible by 2, 3, or 5.  The 8 residues are
>> 1, 7, 11, 13, 17, 19, 23, and 29.  So a single byte can
>> hold all the information needed for 30 numbers, which means
>>
>>     1500000000000 / 30 = 50000000000
>>
>> which is to say 50 gigabytes should suffice.
>
> Show me the code.

Apparently you have missed the point.