約数の個数の偶奇判定。

問題
input:
　整数 n
output:
　k = 整数 n の約数の個数
　とする。このとき k が奇数ならば yes, 偶数ならば no

n の約数を並べてみると、

　 $d_{0}, d_{1}, \cdots, d_{k-1} \qquad(d_{0} = 1, \quad d_{k-1} = n )$

となる。

ここでポイントになるのが次の命題

任意の $i \quad (0 \le i \le k-1)$ について
　 $d_{i} \quad\times\quad d_{k-1-i} \quad =\quad n$
が成り立つ。

つまり、約数列の前から i 番目と後ろから i 番目でペアを作ることができる。
しかし、約数の個数が奇数の場合は、ちょうど真ん中 ( i = (k-1)/2 ) が存在し、ペアを作れない。
このとき、
　 $d_{i}^{2}\quad = \quad n$
すなわち、
　 $d_{i} = \sqrt{n}$
である。

この逆を辿ると、 $\sqrt{n}$ が整数ならば、それは n の約数に含まれ、約数列の中で孤立することがわかる。
ゆえに、k が奇数 ⇔ $\sqrt{n}$ が整数