I suspect it is faster to form digit-wise viable candidates, and cull the ones that are PrimeQ
, than to iterate over explicit primes. The reason is that the percentage of the latter is going to be much smaller than that of the former, hence we can save considerably on the number of iterations and tests. The code below implements this approach.
Timing[Reap[For[j = 1, j < 10^5, j++,
digits = IntegerDigits[FromDigits[IntegerDigits[j, 4]]];
If[Last[digits] == 0 || Last[digits] == 2, Continue[]];
If[Count[digits, 0] < Length[digits]/2, Continue[]];
val = FromDigits[digits];
If[PrimeQ[val], Sow[val]];
]][[2, 1]]]
(* Out[118]= {0.494928, {2003, 3001, 100003, 100103, 102001, 103001,
130003, 200003, 200023, 200033, 200201, 202001, 230003, 300023,
300301, 1000003, 1000033, 1000303, 1001003, 1003001, 1003003,
1010003, 1020001, 2000003, 2000303, 2002001, 2020001, 2020003,
2100001, 2300003, 3000103, 3000301, 3001001, 3001003, 3002003,
3010001, 3200003, 3300001, 10000103, 10000121, 10000223, 10000303,
10001203, 10002203, 10003001, 10003003, 10003031, 10010023,
10010101, 10012001, 10020013, 10020103, 10021001, 10021003,
10023001, 10030003, 10030103, 10033003, 10100011, 10100201,
10102003, 10200011, 10200101, 10200301, 10201001, 10203001,
10220003, 10300013, 10300201, 11002001, 11020001, 11020003,
11200001, 12001001, 12100003, 13000201, 13000301, 13000303,
13200001, 20000003, 20000023, 20000033, 20000213, 20000221,
20000303, 20000311, 20001001, 20001031, 20001203, 20001301,
20002201, 20003003, 20003023, 20003201, 20011001, 20020001,
20020103, 20020303, 20023001, 20030011, 20030203, 20100023,
20100203, 20101001, 20102003, 20130001, 20200013, 20203003,
20300003, 20300011, 20300101, 20300201, 20310001, 21000103,
21003001, 21030001, 21100003, 22000001, 22000003, 22000021,
22000031, 22000103, 22000201, 22010003, 22200001, 22300001,
23000011, 23000101, 23100001, 30000001, 30000023, 30000133,
30000301, 30000323, 30000331, 30001003, 30001031, 30001201,
30001303, 30002023, 30002033, 30002303, 30003101, 30003301,
30010021, 30010033, 30010103, 30010301, 30010303, 30013003,
30030023, 30030031, 30030101, 30100003, 30100201, 30100303,
30101003, 30103001, 30130003, 30200003, 30200011, 30200021,
30200033, 30200201, 30210001, 30300301, 30303001, 30310003,
31000003, 31000301, 31000303, 31002001, 31020001, 31030001,
32000011, 32000303, 32001001, 32010001, 32030003, 33000001,
33000031, 33000103, 100000123, 100000213, 100000223, 100000231,
100001203, 100001303, 100002011, 100002013, 100002031, 100002103,
100003021, 100003301, 100010021, 100010023, 100010033, 100010203,
100020023, 100020103, 100021003, 100022003, 100030001, 100031003,
100120003, 100130003, 100200011, 100200013, 100200031, 100200301,
100203001, 100210001, 100230001, 100300001, 100303003, 100310003,
100330001, 100330003, 101000023, 101000203, 101001001, 102000023,
102002003, 102100001, 102100003, 102300001, 103000201, 103000301,
103010003, 103300003, 110000201, 110002003, 110020003, 120000031,
120000103, 120000203, 120000301, 120001001, 120003001, 120100003}} *)
An iteration to 10^7 takes around 52 seconds and delivers 10151 such values (also 10501 is a prime, though not quite a contender; too bad it wasn't 10301).