No.3037 Toggle Toggle Toggle!
Problem Statement
$N$ people are sitting in a row, and they are assigned the numbers $1$ to $N$ in order starting from the leftmost person.
A sitting person standing up and a standing person sitting down is called toggling.
At the first signal, all the people stand up.
At the next signal, starting from person $2$, every $1$ person is skipped ($2$,$4$,$6$...) and those people toggle.
At the signal after that, starting from person $3$, every $2$ people are skipped ($3$,$6$,$9$...) and those people toggle.
Similarly, at the $i$-th signal, the people whose numbers are multiples of $i$ toggle.
Finally, at the $N$-th signal, only person $N$ toggles.
Find the number of people standing when all the signals have finished.
Constraints
$・$ $2 \le N \leq 10^{18}$
Input
The input is given from standard input in the following format.$N$
Output
Output the number of people standing when all the signals have finished.
Sample
Sample 1
Input
6
Output
2
Initially, $6$ people are sitting in a row, assigned the numbers $1,2,3,4,5,6$ in order from the left end.
At the first signal everyone stands up, and those now standing are ($1,2,3,4,5,6$).
At the $2$-nd signal, persons $2,4,6$ sit down, and those now standing are ($1,3,5$).
At the $3$-rd signal, person $3$ sits down and person $6$ stands up. Those now standing are ($1,5,6$).
At the $4$-th signal, person $4$ stands up, and those now standing are ($1,4,5,6$).
At the $5$-th signal, person $5$ sits down, and those now standing are ($1,4,6$).
At the $6$-th signal, person $6$ sits down, and those now standing are ($1,4$).
When the last signal has finished, $2$ people are standing, so output 2.
Sample 2
Input
50
Output
7
Sample 3
Input
2000
Output
44
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
nauclhlt
naniwazu