Count Numbers with Odd Number of Divisors

Given an integer n, count how many numbers between 1 and n (inclusive) have an odd number of divisors.

A well-known fact is that a number has an odd number of divisors if and only if it is a perfect square. In other words, you are required to compute the largest integer \(k\) such that \(k^2 \leq n\). This is equivalent to finding \(\lfloor \sqrt{n} \rfloor\).

inputFormat

The input consists of a single integer n supplied via standard input (stdin).

It is guaranteed that n is a non-negative integer.

outputFormat

Output a single integer, which is the count of numbers between 1 and n that have an odd number of divisors, i.e. the number of perfect squares not exceeding n, printed to standard output (stdout).

10

3