费马质数定理

任意$4k+1$ 形式的质数都可以写成两个整数的平方和，而$4k+3$ （即$4k-1$）形式的质数则不能。

以 $89$ 为例，$89=4 \times 22 +1$ 又是质数，那么它就可以写成两个数的平方和：$8^2+5^2$ .

而 $6023$ 则不行，因为 $6023=$ $4 \times 1505$$+3$ .

ET 给出一个复杂度为$O(\dfrac{n}{2})$ 的穷举算法：

$\because 4k+1=x^2+y^2$

$\therefore$ $x,y$ 必一奇数一偶数

令 $4k+1=(2m)^2+(2n+1)^2$

化简得：$k=m^2+n(n+1)$

$n$ 从1开始穷举到 $\sqrt{k}$ ，验算 $m$ 是不是整数，如果是，返回x=2m，y=2n+1.