题目描述

塔子哥希望你找出满足$A+B=C^2$,且A,B,C均小于等于N的素数三元组（A,B,C)的数量。

思路:素数筛 + 枚举优化

一个朴素的想法是:1.先得到n以内的素数 2.两重循环枚举$A+B$ , 判断是否是某个素数的平方。

对于第一步，$n = 5e5$ , 需要使用素数筛来加速这个过程。直接暴力判素数$O(n\sqrt{n})$会超时。可以使用埃式筛得到。

对于第二步，我们从第一步得到素数为$4e4$数量级。所以无法直接$O(p^2)$的作循环。但我们观察到这样的对其实很少！

因为$A+B = C^2$ , 那么也就要求$C$不能太大，$C = \sqrt{A+B} \leq \sqrt{2 * 4e4}=282$ 。 那么$[1,282]$ 内的素数就非常稀少了。