Timing[mx = 5000000000; so1 = Flatten[Table[Prime[k]^3 + Prime[k1]^3,
 {k, PrimePi[(mx/2)^(1/3)]}, {k1, k}]];
 so2 = Flatten[Table[Prime[k]^2 + Prime[k1]^2, 
{k, PrimePi[(mx/2)^(1/2)]}, {k1, k}]];
 int = Intersection[so1, so2];]
{40.171875`, Null}

Length @ int
122

int
{370, 7202, 36650, 1345682, 2127890, 2685962, 2715410, 3872090, 
4331090, 4657490, 6379130, 7887458, 12235970, 14386538, 17938730, 
19909370, 22588130, 22665530, 22694978, 30027170, 30080258, 31576970, 
39707642, 40024010, 42567698, 42735530, 48438290, 54517538, 62572970, 
72096050, 82095410, 84611378, 87290138, 99553610, 143085458, 162958178, 
186662450, 192489050, 222764330, 231079322, 232958882, 246313730, 257079170, 
265848050, 265877498, 270840050, 285750218, 286607522, 315278570, 337819970, 
357695858, 366704210, 384247442, 386926202, 399762578, 407026370, 414543890, 
423644258, 431019290, 432958682, 437409002, 455669282, 456403610, 489496250, 
519084722, 527296250, 569949770, 573592682, 609734162, 618016250, 620877458, 
624520370, 632293562, 633869570, 653742290, 664144490, 671838410, 683270642, 
697864130, 785545490, 803966690, 857488322, 858527570, 1033535522, 1064559242, 
1106840810, 1227541250, 1230091490, 1338805442, 1384859810, 1416248210, 
1445563730, 1451561690, 1465678730, 1524845978, 1546806098, 1592696450, 
1609166162, 1634055050, 1655034050, 1739512658, 1791334298, 1949353922, 
1962438770, 1972830890, 2008465058, 2037144818, 2131257098, 2152777898, 
2159565770, 2163164978, 2218568690, 2236289690, 2305588178, 2329417298, 
2341083530, 2373617090, 2422180010, 2462541842, 2771098202, 2958387770, 
3171393290}

Mod[int, 24]
{10, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2}

Do[Do[p = Prime[k]; If[PrimeQ[q = (mx - p^3)^(1/3)], Print[{mx, p, q}]], {k, PrimePi[(mx/2)^(1/3)]}], {mx, int}]
{370, 3, 7}
{7202, 7, 19}
{36650, 19, 31}
{1345682, 37, 109}
{2127890, 43, 127}
{2685962, 7, 139}
{2715410, 31, 139}
{3872090, 13, 157}
{4331090, 7, 163}
{4657490, 3, 167}
{6379130, 127, 163}
{7887458, 19, 199}
{12235970, 61, 229}
{14386538, 73, 241}
{17938730, 181, 229}
{19909370, 19, 271}
{22588130, 139, 271}
{22665530, 7, 283}
{22694978, 31, 283}
{30027170, 103, 307}
{30080258, 3, 311}
{31576970, 97, 313}
{39707642, 151, 331}
{40024010, 223, 307}
{42567698, 271, 283}
{42735530, 61, 349}
{48438290, 181, 349}
{54517538, 229, 349}
{62572970, 13, 397}
{72096050, 283, 367}
{82095410, 97, 433}
{84611378, 19, 439}
{87290138, 139, 439}
{99553610, 67, 463}
{143085458, 31, 523}
{162958178, 271, 523}
{186662450, 79, 571}
{192489050, 73, 577}
{222764330, 313, 577}
{231079322, 241, 601}
{232958882, 421, 541}
{246313730, 283, 607}
{257079170, 271, 619}
{265848050, 7, 643}
{265877498, 31, 643}
{270840050, 3, 647}
{285750218, 271, 643}
{286607522, 367, 619}
{315278570, 367, 643}
{337819970, 199, 691}
{357695858, 109, 709}
{366704210, 523, 607}
{384247442, 19, 727}
{386926202, 139, 727}
{399762578, 181, 733}
{407026370, 151, 739}
{414543890, 439, 691}
{423644258, 43, 751}
{431019290, 421, 709}
{432958682, 211, 751}
{437409002, 571, 631}
{455669282, 97, 769}
{456403610, 397, 733}
{489496250, 607, 643}
{519084722, 487, 739}
{527296250, 523, 727}
{569949770, 61, 829}
{573592682, 157, 829}
{609734162, 571, 751}
{618016250, 439, 811}
{620877458, 61, 853}
{624520370, 157, 853}
{632293562, 397, 829}
{633869570, 31, 859}
{653742290, 271, 859}
{664144490, 613, 757}
{671838410, 601, 769}
{683270642, 367, 859}
{697864130, 3, 887}
{785545490, 211, 919}
{803966690, 487, 883}
{857488322, 607, 859}
{858527570, 661, 829}
{1033535522, 349, 997}
{1064559242, 61, 1021}
{1106840810, 349, 1021}
{1227541250, 181, 1069}
{1230091490, 307, 1063}
{1338805442, 379, 1087}
{1384859810, 733, 997}
{1416248210, 7, 1123}
{1445563730, 373, 1117}
{1451561690, 691, 1039}
{1465678730, 367, 1123}
{1524845978, 3, 1151}
{1546806098, 241, 1153}
{1592696450, 883, 967}
{1609166162, 151, 1171}
{1634055050, 829, 1021}
{1655034050, 811, 1039}
{1739512658, 193, 1201}
{1791334298, 829, 1069}
{1949353922, 97, 1249}
{1962438770, 241, 1249}
{1972830890, 883, 1087}
{2008465058, 523, 1231}
{2037144818, 673, 1201}
{2131257098, 643, 1231}
{2152777898, 103, 1291}
{2159565770, 199, 1291}
{2163164978, 823, 1171}
{2218568690, 757, 1213}
{2236289690, 439, 1291}
{2305588178, 73, 1321}
{2329417298, 619, 1279}
{2341083530, 163, 1327}
{2373617090, 409, 1321}
{2422180010, 691, 1279}
{2462541842, 829, 1237}
{2771098202, 937, 1249}
{2958387770, 907, 1303}
{3171393290, 1129, 1201}


Do[Do[r = Prime[k]; If[PrimeQ[s = (mx - p^2)^(1/2)], 
Print[{mx, r, s}]], {k, PrimePi[(mx/2)^(1/2)]}], {mx, int}]
{370, 3, 19}
{7202, 31, 79}
{7202, 59, 61}
{36650, 13, 191}
{1345682, 491, 1051}
{2127890, 293, 1429}
{2685962, 439, 1579}
{2715410, 307, 1619}
{3872090, 461, 1913}
{3872090, 1307, 1471}
{4331090, 23, 2081}
{4657490, 439, 2113}
{4657490, 1427, 1619}
{6379130, 953, 2339}
{7887458, 797, 2693}
{12235970, 1163, 3299}
{12235970, 1433, 3191}
{12235970, 1693, 3061}
{14386538, 443, 3767}
{14386538, 1667, 3407}
{17938730, 233, 4229}
{17938730, 701, 4177}
{19909370, 211, 4457}
{19909370, 313, 4451}
{19909370, 1423, 4229}
{19909370, 2081, 3947}
{22588130, 127, 4751}
{22588130, 919, 4663}
{22588130, 2311, 4153}
{22588130, 2749, 3877}
{22665530, 599, 4723}
{22694978, 1993, 4327}
{30027170, 937, 5399}
{30080258, 883, 5413}
{30080258, 2347, 4957}
{30080258, 2897, 4657}
{30080258, 3673, 4073}
{31576970, 2543, 5011}
{31576970, 3529, 4373}
{39707642, 71, 6301}
{40024010, 3163, 5479}
{42567698, 1283, 6397}
{42735530, 3761, 5347}
{48438290, 103, 6959}
{48438290, 2617, 6449}
{54517538, 2963, 6763}
{62572970, 2039, 7643}
{72096050, 3229, 7853}
{82095410, 173, 9059}
{82095410, 5297, 7351}
{84611378, 3137, 8647}
{87290138, 1997, 9127}
{99553610, 461, 9967}
{99553610, 4663, 8821}
{99553610, 5657, 8219}
{143085458, 5413, 10667}
{162958178, 7537, 10303}
{186662450, 6833, 11831}
{192489050, 4219, 13217}
{222764330, 6221, 13567}
{231079322, 2269, 15031}
{232958882, 349, 15259}
{232958882, 5279, 14321}
{246313730, 4957, 14891}
{246313730, 4969, 14887}
{246313730, 9049, 12823}
{246313730, 9787, 12269}
{246313730, 10303, 11839}
{257079170, 3121, 15727}
{257079170, 10709, 11933}
{265848050, 10369, 12583}
{265877498, 1997, 16183}
{270840050, 1777, 16361}
{270840050, 7933, 14419}
{285750218, 197, 16903}
{285750218, 6397, 15647}
{286607522, 6211, 15749}
{286607522, 7121, 15359}
{315278570, 3191, 17467}
{315278570, 11549, 13487}
{337819970, 3257, 18089}
{357695858, 5657, 18047}
{366704210, 3323, 18859}
{384247442, 11789, 15661}
{386926202, 6791, 18461}
{399762578, 3257, 19727}
{399762578, 10333, 17117}
{407026370, 6553, 19081}
{414543890, 3313, 20089}
{414543890, 9403, 18059}
{414543890, 11717, 16651}
{423644258, 10627, 17627}
{431019290, 11299, 17417}
{432958682, 881, 20789}
{437409002, 11171, 17681}
{455669282, 6151, 20441}
{456403610, 3583, 21061}
{456403610, 12511, 17317}
{489496250, 12227, 18439}
{519084722, 11801, 19489}
{527296250, 1091, 22937}
{527296250, 9829, 20753}
{527296250, 11411, 19927}
{527296250, 15149, 17257}
{569949770, 5861, 23143}
{569949770, 13487, 19699}
{569949770, 15773, 17921}
{573592682, 1559, 23899}
{573592682, 8609, 22349}
{573592682, 9871, 21821}
{573592682, 16889, 16981}
{609734162, 5011, 24179}
{618016250, 3907, 24551}
{620877458, 5437, 24317}
{624520370, 9221, 23227}
{624520370, 13049, 21313}
{624520370, 17011, 18307}
{632293562, 4759, 24691}
{633869570, 7547, 24019}
{633869570, 11681, 22303}
{653742290, 7901, 24317}
{653742290, 11059, 23053}
{653742290, 11807, 22679}
{664144490, 7, 25771}
{664144490, 1399, 25733}
{671838410, 9743, 24019}
{671838410, 14957, 21169}
{683270642, 11909, 23269}
{697864130, 79, 26417}
{785545490, 181, 28027}
{785545490, 3541, 27803}
{803966690, 433, 28351}
{857488322, 19661, 21701}
{858527570, 12713, 26399}
{1033535522, 6221, 31541}
{1033535522, 12941, 29429}
{1064559242, 14699, 29129}
{1106840810, 5333, 32839}
{1227541250, 3121, 34897}
{1230091490, 8363, 34061}
{1338805442, 19531, 30941}
{1338805442, 25229, 26501}
{1384859810, 22511, 29633}
{1416248210, 6211, 37117}
{1416248210, 17923, 33091}
{1445563730, 853, 38011}
{1451561690, 2791, 37997}
{1451561690, 14083, 35401}
{1451561690, 25031, 28723}
{1465678730, 12979, 36017}
{1524845978, 27277, 27943}
{1546806098, 1693, 39293}
{1546806098, 2837, 39227}
{1592696450, 25411, 30773}
{1609166162, 3389, 39971}
{1634055050, 2549, 40343}
{1634055050, 8849, 39443}
{1655034050, 13669, 38317}
{1739512658, 7393, 41047}
{1739512658, 27077, 31723}
{1791334298, 313, 42323}
{1791334298, 13127, 40237}
{1949353922, 1409, 44129}
{1962438770, 2113, 44249}
{1972830890, 1777, 44381}
{2008465058, 6397, 44357}
{2008465058, 23473, 38177}
{2037144818, 23827, 38333}
{2131257098, 6053, 45767}
{2131257098, 20743, 41243}
{2152777898, 22283, 40697}
{2159565770, 5273, 46171}
{2159565770, 8059, 45767}
{2163164978, 24767, 39367}
{2218568690, 8807, 46271}
{2218568690, 25733, 39451}
{2218568690, 31079, 35393}
{2236289690, 2543, 47221}
{2236289690, 16619, 44273}
{2236289690, 30367, 36251}
{2305588178, 22283, 42533}
{2305588178, 26777, 39857}
{2329417298, 23977, 41887}
{2341083530, 23143, 42491}
{2373617090, 1993, 48679}
{2373617090, 26431, 40927}
{2422180010, 22147, 43951}
{2462541842, 6389, 49211}
{2771098202, 26489, 45491}
{2958387770, 13469, 52697}
{2958387770, 22961, 49307}
{3171393290, 18787, 53089}
{3171393290, 31277, 46831}