\(x^2-y=z^2\) を満たす非負整数 \(z\) が存在するとします． この時，\(x^2-z^2=(x+z)(x-z)=y\) と式を書き直すことができます．

\(p=x+z,q=x-z\) とおき，以下の条件を満たす整数 \(p,q\) を数える問題に変形します．

• \(p \geq q\)
• \(x=(p+q)/2\) は整数
• \(1 \leq x=(p+q)/2 \leq N\)
• \(1 \leq y=pq \leq N\)

これらの条件から，まず \(p,q\) が正整数であることがわかります． またさらに，\(pq \leq N\) より，\((p+q)/2 \leq N\) は自動的に従います．

ここで，\(q \leq \sqrt{N}\) より，\(q\) としてあり得る値をすべて試すことができます． そして，\(q\) の値を決めてしまえば，\(p\) としてありうる値は，\(q \leq p \leq N/q\) かつ \(p \equiv q \bmod 2\) を満たすものだとわかり，これは \(O(1)\) で数えることができます．

よって，全体で \(O(\sqrt{N})\) でこの問題を解くことができます．