AbsoluteTiming[
 f[n_, k_] := PrimeQ@FromDigits@RotateLeft[IntegerDigits[n], k];
 g[n_] := And @@ Table[f[n, k], {k, 1, IntegerLength@n}];

 ans = Length@
   Parallelize@Select[Prime[Range[1, PrimePi[10^6 - 1]]], g]]