808. 可反转质数平方(Reversible prime squares)
169和961都是质数的平方，且将169翻转后即可得到961，则我们称一个数为可翻转质数平方，若其满足以下条件：
- 它不是回文数
- 它是质数的平方
- 将它的数字反转所得的数也是质数的平方
169和961都不是回文数，因此它们都是可反转质数平方。求前五十个可反转质数平方的和。
分析：此题可使用简单暴力方法解决，首先我们可以筛选出特定范围的质数(经测试，三千二百万是一个恰当的上界)，然后计算这些质数的平方并将其保存的集合中，之所以要使用集合是因为集合中的\(in\)操作是常数时间复杂度。对于每个质数，我们计算它的平方，判断其是否为回文数，并判断其反转是否也在素数的平方集合中，如果在则一个满足题目要求的解。如此找到五十个质数平方，再求其和即可。代码如下：
# time cost = 2.85 s ± 86.9 ms
import numpy as np
def prime_sieve(n):
sieve = np.ones(n//3+(n%6==2), dtype=bool)
sieve[0] = False
for i in range(int(n**0.5)//3+1):
if sieve[i]:
k=3*i+1|1
sieve[((k*k)//3)::2*k] = False
sieve[(k*k+4*k-2*k*(i&1))//3::2*k] = False
return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]
def main(n=32000000):
res = 0
p_squares = set(p*p for p in prime_sieve(n))
for p in p_squares:
rp = int(str(p)[::-1])
if p != rp and rp in p_squares:
res += p
return res