Switching between Sieving and Primality testing

[JASory]

Sieving is particularly good at producing huge amounts of primes, particularly small ones and in sequential (or roughly sequential order). However their is some crossover point when the integers get large enough and the interval gets small enough that all the precomputation needed to sieve is slower than simply checking all the integers with a individual primality test.

From my comparisons of Machine-Prime and primesieve (the fastest primality testing and sieving software respectively), it seems that the crossover is around 100 million integers near 2^64 (i.e calling a fast primality test for less than 100 million integers around 2^64 is faster than sieving). I haven't benchmarked this program to see what the crossover point is but I suspect it is much higher and is something worth looking into. It would also save a considerable amount of memory.

[JSorngard]

That is a very good point. If I understood you correctly something like sieve_geq should have a point for large enough lower_limit and small enough N where it is faster to just call is_prime on each of the numbers?

That makes a lot of sense. I'll make some benchmarks to try to find the crossover point for this library. Thank you so much for the insight!

Always going directly for using the primality test would make the API of those functions much nicer as well, but I think a combined approach could be made to work.