Если
является полным квадратом, то
-- тоже. Если
не является полным квадратом и нечетно, то степени простых не являются одновременно четными, наоборот, если
четно, то
-- полный квадрат.
Итак, искомое число равно количеству нечетных квадратов и четных чисел. То есть
. Подсчет дает
.