5jt / primes Goto Github PK

When the cache of known primes KP is long, finding primes to an x close to PT is faster (KP where KP<=x) is faster than sieving. But finding primes to an x much smaller than PT is slower, because it requires KP comparisons to select.

If we knew the highest prime below x in KP we could find it fast (because KP is sorted) and select with (KP?hp)#KP.

But we don’t. Is there a way to test items of KP for <=x and stop when we find the first?

Otherwise we could use a test on PT and x to decide when to select from KP and when to sieve.

Interestingly, sieving from scratch turns out to be (much, much) faster than reconstructing the bitmap from KP.