cant

the end of the block you park it at 524'295, at which point it tumbles to near the bottom of the heap. Then you pick 13 off the heap, mark off all the multiples of 13, etc. Once you're done striking off all the composites in the block, you iterate over its primes, inserting a rider for each of them into the heap (at their square, so for example the rider for 262'147 starts running at 68'721'049'609), maybe outputting them to a file, and then you can discard the block. That means you only need to keep the heap of known primes in RAM, not the bitmap of all the numbers you contemplate testing for primality. This not only allows you to change your mind about how many you want, it reduces your space by a factor of the natural logarithm. But this doesn't beat the constant factor for a long time; https://en.wikipedia.org/wiki/Prime-counting_function says π(10¹¹) = 4'118'054'813, so 64 GiB of RAM should be enough to calculate all the primes up to 10¹¹ if each heap element is two 64-bit integers; while, without a heap of riders, with one bit each, you would only need 12 GiB. Well, 6 GiB skipping the evens. If, instead of discarding the already finished blocks, you lazily add riders for their primes when you reach those primes' squares, you can do a lot better up to a much higher sieve size: at 10¹¹ you've just passed 316'271², so your heap only needs to contain the 27'296 primes p such that 2 < p ≤ 316'271, thus occupying only 436'736 bytes. Moreover, if you do know ahead of time where you're going to stop, you can still discard the finished blocks whose primes will never spawn riders in the heap. This approach should allow you to sieve out the 201'467'286'689'315'906'290 prime numbers up to 10²² in those same 64 GiB of RAM, but an earlier obstacle is that striking off 10²² composites at one per nanosecond would take you several hundred millennia. You don't want to use a standard bin-heap at gigabyte sizes on a cached machine because you'll have one cache miss per access once you get outside the top few levels of the heap. Instead, you probably want to block it into a heap of heaps, staggered so their roots aren't a large power of 2 apart. Or possibly use a Fibonacci heap, if you can understand it. It might make sense to bundle the first few primes into a "wheel", with, say, period 15'015 (3 · 5 · 7 · 11 · 13 · 17), where you just OR an appropriately shifted bitmap into the block to strike off all their multiples at once (9255 out of every 15'015 numbers in this case), instead of striking off their multiples one by one with the rider mechanism. Better still would be if you can work out an efficient addressing scheme which doesn't even assign a bit index to numbers that are divisible by one of these small primes, a generalization of the just-skip-the-evens trick. These are just some things that have occurred to me (though I'm pretty sure I read about the wheel trick somewhere), so probably there are already more efficient implementations known of the Sieve of Eratosthenes, and I just haven't heard of them. Edit: Darius Bacon wrote a version of this approach in https://github.com/darius/cant/blob/master/library/factoring... where the "frontier" of active riders is stored in a hash table rather than a bin heap, which is almost certainly a more efficient approach. But he's not doing the bitmaps, and the overhead of Cant makes it hard to measure the absolute efficiency of the approach.

ife's divorce lawyer (as Kragen put it). Back in the day a lot of us thought we had a different kind of relationship with C compilers, and it'd be fine to code to that informal social contract. (Just a loose analogy.) I'm piddling away at https://github.com/darius/cant these days. (Some of the motivation was feeling too confined by Python, actually.) No Wasm, but I'm happy it exists! I tried to make a system like it 20 years ago (Idel) and gave up too soon.