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

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.