[yukicoder] No. 843 Triple Primes

問題

方針

素数の列挙

エラトステネスの篩を用いて素数を列挙します。

制約を考える

\( p + q = r^2 \) を満たすので、\( p, q, r \) のうち、二つの変数を探索すればいいことが分かります。ここで、\( 2 \leq p, q, r \leq N \) です。また、方程式から、\( r \) について、

\[
\begin{eqnarray}
2 &\leq& p \leq N\\
2 &\leq& r^2 – q \leq N\\
2 + q &\leq& r^2 \leq N + q\\
\sqrt{2 + q} &\leq& r \leq \sqrt{N + q} \ (r > 1)
\end{eqnarray}
\]

を満たす必要があります。したがって、\( q, r \) について全探索を行います。

コード