I rewrote your primeG, ignorant of clever methods. Nevertheless, with [[All,1]] and the fourth argument to Position you can get a 50% speed increase. Also, since you already calculate the primes in aa, there is no need to use Prime in calculating dd.
MartinPrimeGaps[nn_]:=
With[{aa = Prime@Range@PrimePi@nn},
With[{bb = Differences[aa]},
With[{cc = Split[Nest[Split[#, Greater][[All, 1]] &, bb,
Round@(Log@nn^2)]][[All, 1]]},
Transpose[{cc - 1,
aa[[Flatten[Position[bb, #, 1, 1] & /@ cc]]]}]]]]
Update
I rewrote primeGmax in two different ways. The first MaxPrimeGap1 uses a lot of memory when a large range is required, and is cleaner but not significantly faster than primeGmax.
MaxPrimeGap1[r1_?OddQ, r2_] :=
Block[{p = Range[r1, r2, 2], gaps, maxgap},
gaps = Differences[p = Pick[p, PrimeQ[p]]] - 1;
maxgap = Max[gaps];
{maxgap, p[[Position[gaps, maxgap, 1, 1][[1, 1]]]]}]
The second MaxPrimeGap2 uses almost no memory, but NextPrime makes it significantly slower than MaxPrimeGap1.
MaxPrimeGap2[r1_?OddQ, r2_] :=
Block[{p1 = r1, p2 = NextPrime[r1], g, b = {0, 0}},
g = {p2 - p1 - 1, p1};
While[p1 < r2,
p2 = NextPrime[p1];
g = {p2 - p1 - 1, p1};
p1 = p2;
If[g[[1]] > b[[1]], b = g]
];
b]
The slow part of the code is testing for primality. Specifying only odd numbers in the Range statement cuts the number of tests in half. Sieve methods, which continue cutting numbers in the range, are very fast. I rewrote code from @SimonWoods here to return a list of candidate numbers between nmin and nmax not divisible by the first m primes.
CandidatePrimes[nmin_Integer, nmax_Integer, m_Integer] :=
Module[{y = Range[nmin, nmax], min, max = nmax - nmin + 1},
Map[If[(min = # - Mod[nmin, #] + 1) <= max, (y[[min ;; max ;; #]] = 0)] &,
Prime[Range[m]]];
SparseArray[y]["NonzeroValues"]]
Now use CandidatePrimes to reduce the number of prime checks.
MaxPrimeGap3[r1_?OddQ, r2_Integer, m_Integer] :=
Block[{p = CandidatePrimes[r1, r2, m], gaps, maxgap},
gaps = Differences[p = Pick[p, PrimeQ[p]]] - 1;
maxgap = Max[gaps];
{maxgap, p[[Position[gaps, maxgap, 1, 1][[1, 1]]]]}]
If you have parallel processors, then it is faster to use Pick[p,ParallelMap[PrimeQ,p]] instead of Pick[p,PrimeQ[p]. Call this version MaxPrimeGap4.
Set the lower limit to a large prime, NextPrime[10^12].
AbsoluteTiming[MaxPrimeGap1[1000000000039, 1000000000039 + 10^7]]
(* {16.682, {321, 1000008002317}} *)
AbsoluteTiming[MaxPrimeGap3[1000000000039, 1000000000039 + 10^7, 300]]
(* {13.427, {321, 1000008002317}} *)
Using 8 parallel kernels, MaxPrimeGap4 takes 3.9 s. Another example:
AbsoluteTiming[MaxPrimeGap4[1000000000000037, 1000000000000037 + 10^8, 1000]]
(* {36.631, {489, 1000000025764111}} *)
