Number of perfect squares less than N? What is the process used to find the number of perfect squares less than or equal to N?
 A: Hint: It will be equal to the number of positive integers less than or equal to $\sqrt{N}$.
A: The other answers here are correct, but I would like to explain why they work. It's because the square of any whole number is greater than the squares of smaller whole numbers. For example, the square of 5 (25) is greater than the square of 4, 3, 2, and 1 (16, 9, 4, and 1, respectively). Therefore, the number of squares smaller than the square of a number, is the number of whole numbers less than it.
A: Hint: It will be equal to the floor function of $\sqrt N$
A: Since you asked for a process (suggesting an algorithm), it's worth mentioning in addition to the other answers that
$$
\lfloor \sqrt{n} \rfloor
$$
can be calculated in time polynomial in $\log n$, as follows:


*

*Do a binary search for the answer: of $\log_2 n$ possible bits first test the largest first bit that will work, then the largest second bit that will work for that first bit, and then the largest third bit that will work for those two initial bits, and so on.

*For each bit check, we have to square a number in binary with $\log n$ digits, which will take polynomial time in $\log n$.
