Your questions made me go do some work on this. It's not released yet, but on github.
time perl -Mbigint -Mntheory=:all -E 'say join " ", Math::Prime::Util::GMP::sieve_prime_cluster(1,1e11, 2,6,8,12,18,20,26,30,32);'
11 33081664151 83122625471
time perl -Mbigint -Mntheory=:all -E 'say join " ", Math::Prime::Util::GMP::sieve_prime_cluster(1e19,1e19+1e13, 2,6,8,12,18,20,26,30,32);'
In some examples I've looked at,
polysieve2 is slightly faster, assuming you tune the sieve sizes. Bad sieve size choices can make it much slower. It quite likely is much faster on some other cluster combinations. Your mileage may vary. The times from JKA's posts suggest his old code is very fast. There are some OEIS sequences for long clusters that imply someone either had a lot of time or has a really fast program.
- Use a primorial, e.g. 23# to generate a list of acceptable residues. I try to choose an appropriate primorial size, stopping at 23# (to keep all residues under 31 bits) or earlier if we have more than ~50k residues or the given range is small. But you could just pick something. Matt Anderson uses 13# (30030) for his examples, JKA uses 31#. Larger primorials are more efficient but the overhead starts growing.
- Walk through the range in chunks of the primorial size. We'd like to efficiently sieve further, which can be done using only the base+residue locations. For primes larger than the primorial prime and the chosen depth (e.g. 1000), we can check divisibility of the offset residues. If dealing with bigints this is especially nice as only a single bigint modulo is needed per prime, with the rest all being 32-bit calculations. With a large range you could optimize a bit more and do some of these modulos once before you start walking the range then simple boolean computations can be done for a few of the first primes. I'm doing that and it really helps.
polysieve2 is quite fast at this step.
- Do primality tests on the residues that are left. Step 1 guaranteed that none of the locations checked have factors <= your primorial prime. Step 2 made sure nothing has factors under your sieve depth.
polysieve2 doesn't do this step, meaning you use something else for the final tests.
Step 2 is where most of my time is spent, but of course it's more efficient to at least spend some time there. Step 1 is pretty straightforward, and if you have a favorite cluster you can do it once by hand if you desired. This simple thing greatly reduces the number of tests needed. For this cluster, step 1 gets us down to 8190 residues per 223092870 values. Step 2 reduces this to under 5 residues left on average with a depth of 1000. Step 3 does the final check. For the second example (10^19 to 10^19+10^13) it ended up doing 289341 total BPSW tests. Typically this is a small part of the time (but may be quite large if the numbers are huge).
The details vary, but I think most of the programs I've seen go through those steps. 1. Use a primorial to find acceptable residues. 2. As we walk the range in primorial-sized steps, sieve further to reduce even more. 3. Primality tests.