Path: ...!weretis.net!feeder9.news.weretis.net!news.quux.org!eternal-september.org!feeder2.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: Re: Sieve of Erastosthenes optimized to the max
Date: Mon, 04 Nov 2024 03:56:28 -0800
Organization: A noiseless patient Spider
Lines: 30
Message-ID: <86h68ntdoz.fsf@linuxsc.com>
References: <ul41d4$2koct$1@raubtier-asyl.eternal-september.org> <861q3o5do1.fsf@linuxsc.com> <v7tdts$29195$1@dont-email.me> <868qx45v5g.fsf@linuxsc.com> <v9lbns$11alj$1@dont-email.me> <86r0aojx1m.fsf@linuxsc.com> <v9o2kf$1gqv1$1@raubtier-asyl.eternal-september.org> <va09jq$30cvv$1@dont-email.me> <va2ca2$3e60e$1@raubtier-asyl.eternal-september.org> <va2cfr$3e9l1$1@raubtier-asyl.eternal-september.org> <va2hq5$3f1gl$1@dont-email.me> <86v7zn3xwk.fsf@linuxsc.com> <vajji3$2rbid$1@raubtier-asyl.eternal-september.org> <vb2if8$1jqts$2@dont-email.me> <86tteyrad0.fsf@linuxsc.com> <vb7efc$3dfh8$1@dont-email.me> <86wmiw3vk2.fsf@linuxsc.com> <871q13sdv3.fsf@nosuchdomain.example.com> <vdj872$36t95$1@dont-email.me> <86msjfzzry.fsf@linuxsc.com> <vf2qel$cko5$3@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Mon, 04 Nov 2024 12:56:31 +0100 (CET)
Injection-Info: dont-email.me; posting-host="f359696380662fa6462481cb0fc8fe02";
	logging-data="967962"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+N1bTFsRNQftcyMGcUwXy6BeFlAXXVmw8="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:A/3j00M1JJ5rQ+HH6/jb3KhRoIo=
	sha1:y1m1ckZ/ryS+3KjxnooRd2JUOh0=
Bytes: 3159

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

> On 07/10/2024 16:41, Tim Rentsch wrote:
>
>> This reaction, more broadly, has been rather surprising.  The whole
>> point of using a sieve is that it is asymptotically faster.  Who
>> cares about how fast primes under a billion, or ten billion, or
>> fifty billion, can be computed?  It's much more interesting to ask
>> how high a limit can be searched in a day or a week of computing.
>> (I don't mean just your comment, but comments from other folks
>> bragging about how fast they can find all 32-bit primes.)  I ran
>> my earlier programs up to limits of 3 trillion or so.
>
> My programs all require the sieved prime map to fit in RAM.  Which in
> my system limits me to about 10^11 primes.
>
> It has occurred to me to extend it for much larger numbers, by paging
> out to disc files.  But I've wasted far too much time on this already!

I propose a new challenge:  compute all primes up to a large number
(e.g., 10e12) with a program that has a small memory footprint (and
no storing intermediate values on disk, etc).

I wrote a small program in C, with a memory footprint well under
one megabyte, and found all primes under 10240000000000 (all it
did was count them, which I checked using primesieve).  About 150
lines of fairly routine C code.

If you want a sanity check there are 354080024725 primes less
than 10240000000000.