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.