会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员，或
购买
该题目所属题库
，可解锁完整内容。
思路:素数筛 + 枚举优化
一个朴素的想法是:1.先得到n以内的素数 2.两重循环枚举A+B , 判断是否是某个素数的平方。
对于第一步，n=5e5 , 需要使用素数筛来加速这个过程。直接暴力判素数O(nn)会超时。可以使用埃式筛得到。
对于第二步，我们从第一步得到素数为4e4数量级。所以无法直接O(p2)的作循环。但我们观察到这样的对其实很少！
因为A+B=C2 , 那么也就要求C不能太大，C=A+B≤2∗4e4=282 。 那么[1,282] 内的素数就非常稀少了。
