No.2392 Sum of Two Squares
Problem Statement
A prime number $P$ is given as input.
Determine whether there exists a pair of positive integers $(i,j)$ satisfying $P = i^2 + j^2$.
Input
The input is given from standard input in the following format:$P$
Constraints
The input satisfies the following constraints:
- $P$ is a prime number at most $10^8$
Output
Print Yes if there exists a pair of positive integers $(i,j)$ satisfying $P = i^2 + j^2$, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
3
Output
No
We have $1^2 + 1^2 = 2 < 3$, and for any positive integers $i,j$ satisfying $(i,j) \neq (1,1)$, we have
$\displaystyle i^2 + j^2 \geq 2^2 + 1^2 = 5 > 3 $
.
Sample 2
Input
5
Output
Yes
We have $2^2 + 1^2 = 5$.
Sample 3
Input
7
Output
No
We have $\displaystyle \begin{array}{rcl} \displaystyle 1^2 + 1^2 &\displaystyle = &\displaystyle 2 < 7 \\ \displaystyle 2^2 + 1^2 &\displaystyle = &\displaystyle 5 < 7 \\ \displaystyle 2^2 + 2^2 &\displaystyle = &\displaystyle 8 > 7 \end{array} $
and for any positive integers $i,j$ satisfying $(i,j) \neq (1,1), (2,1), (2,2)$, we have
$\displaystyle i^2 + j^2 \geq 3^2 + 1^2 = 10 > 7 $
.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
MZKi