yukicoder No.843 Triple Primes 解説

問題

$ p+q=r^2

$ p,q,r \leq N

なる素数(p,q,r)の組の数を数えよ。

解法

$ r^2=p+q \leq 2N より $ r \leq \sqrt{2N}。$ pを$ 2から$ Nまで、$ rを$ 2から$ \sqrt{2N}まで全探索し、$ q=r^2-pなる素数が存在するか二分探索などで判定する。N=500000以下の素数は41538個、$ \sqrt{2N}=1000以下(N=500000)の素数の個数は168個しかないから十分間に合う。