Actually one can do quite well in regions above the working zone of
Prime. Say we want to get the first n primes larger than m, and we intend to parallelize over nproc processors. We can get reasonable approximations of where the n/nproc groupings begin, overshoot each by some fraction, and take Union at the end. Also in case we underdo the total we may need a final run to make up the deficit. The code below does what I have described here.
nPrimesAboveM[m_, n_, nproc_] := Module[
{markers, res, primes, frac = Ceiling[105/100*n/nproc] + 5},
markers =
Round[NestList[# + NIntegrate[Log[x], {x, #, # + n/nproc}] &, m,
nproc - 1]];
primes =
ParallelTable[NextPrime[markers[[j]], Range[frac]], {j, nproc}];
res = Partition[primes, 2, 1];
Map[If[Last[#[[1]]] < First[#[[2]]], Print["sinister gap"]] &,
res];
res = Union @@ primes;
If[Length[res] < n,
res = Join[res, NextPrime[Last[res], Range[n - Length[res]]]]];
Take[res, n]
]
Here is an example, finding a million primes after 10^20.
AbsoluteTiming[plist1 = nPrimesAboveM[10^20, 10^6, 4];]
Out[47]= {111.080568, Null}
It is around 3x faster than its nonparallelized counterpart.
AbsoluteTiming[plist2 = NextPrime[10^20, Range[10^6]];]
Out[10]= {366.245392, Null}
plist2 === plist1 (* check result *)
Out[48]= True
One important caveat: it is not flawless. I have not put in a patch for the case where we get a gap, and this case can arise.
