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

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

From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c++
Subject	Re: OT: Re: Sieve of Erastosthenes optimized to the max
Date	2024-11-04 03:56 -0800
Organization	A noiseless patient Spider
Message-ID	<86h68ntdoz.fsf@linuxsc.com> (permalink)
References	(16 earlier) <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>

Show all headers | 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