Groups > comp.lang.c++ > #120831

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

Path	csiph.com!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> (permalink)
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=
Xref	csiph.com comp.lang.c++:120831

Show key headers only | View raw

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.

Back to comp.lang.c++ | Previous | Next — Previous in thread | Find similar

Thread

Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-09-28 03:46 -0700
  Re: OT: Re: Sieve of Erastosthenes optimized to the max Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-09-28 13:49 -0700
    Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-02 11:44 +0100
      Re: OT: Re: Sieve of Erastosthenes optimized to the max Bonita Montero <Bonita.Montero@gmail.com> - 2024-10-02 13:10 +0200
      Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-10-07 08:41 -0700
        Re: OT: Re: Sieve of Erastosthenes optimized to the max Vir Campestris <vir.campestris@invalid.invalid> - 2024-10-20 12:44 +0100
          Re: OT: Re: Sieve of Erastosthenes optimized to the max Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-11-04 03:56 -0800

csiph-web