Một số nguyên dương \(N\) có số lượng ước số lẻ khi và chỉ khi \(N\) là một số chính phương (tức là tồn tại số nguyên \(x\) sao cho \(x^2 = N\)).

• Chứng minh: Các ước số của một số thông thường luôn đi thành từng cặp \((d, N/d)\). Ví dụ ước của 12 là \((1, 12), (2, 6), (3, 4)\) (số lượng ước luôn chẵn).
• Tuy nhiên, nếu \(N\) là số chính phương, sẽ có một cặp ước trùng nhau là \((\sqrt{N}, \sqrt{N})\). Số \(\sqrt{N}\) đứng một mình không ghép cặp với số khác, làm tổng số lượng ước trở thành số lẻ.

Do đó, ta chỉ cần kiểm tra xem \(N\) có phải số chính phương hay không. Trong C++, ta tính \(x = \lfloor \sqrt{N} \rfloor\) và kiểm tra xem \(x \times x == N\) hay không. Độ phức tạp là \(O(1)\).