AbsoluteTiming[
 nMax = 4;
 f[{a_, b_}] := Prime[a] + 2*b^2;
 g[x_] := ! PrimeQ[x] && OddQ[x];
 lst1 = Select[Range[3, 10^nMax], g];
 lst2 = Select[
   Map[f, Tuples[{Range[2, 10^(nMax - 1)], Range[10^nMax]}]], g];
 ans = First[Complement[lst1, lst2]]]