104005 - 开关灯2

将n个灯泡编号为1、2、3、……、n,开始时,灯泡全不亮。 现有n个人去拉开关,第一个人把1的倍数的灯号开关都拉一下,第二个人把2的倍数的灯号都拉一下,第三个人把3的倍数的灯号都拉一下,……直到第n个人将第n号灯泡都拉一下。请问:这n个人全拉完后,有多少个灯泡是亮的?

输入

输入一个整数n(1<n\le1 000 000 000)

输出

输出一个整数,表示有多少个灯泡是亮的。

样例

输入

100

输出

10

提示

因为数据规模大,朴素的模拟算法可能会超时。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题