国王的游戏
描述

今天ACM王国里有n 个死刑犯要被处死，但是他们中间有一部分人很幸运，可以被释放出去，因为今天国王很开心。但是国王很纠结放谁出去，也不想放很多人出去，所以国王决定和死刑犯们玩个游戏。

因为国王很喜欢点人的编号，所以这n 个死刑犯分别被赋予了1到n的编号。国王一共会进行 n 轮游戏。第一轮，国王会点所有人的编号；第二轮，国王会点所以能被 2 整除的编号；第三轮，国王会点所以能被 3 整除的编号，以此类推，第 n 轮，国王只会点编号 n。

同时，国王还非常喜欢奇数，只有在这n轮游戏中，编号一共被点过奇数次的死刑犯才会被释放。现在，国王想问问你，他将放出多少个死刑犯。

输入
一个整数n

输出
一个整数，表示有多少死刑犯将被释放

输入样例 1

3
输出样例 1

1
提示

n<=1e9

这个问题可以通过数学方法来解决。首先，我们需要理解国王点编号的规则和释放死刑犯的条件。根据题目描述，一个编号被点奇数次的死刑犯会被释放。这意味着我们需要找出1到n中所有编号被点奇数次的数量。

一个数被点的次数取决于它的因数。例如，数字6可以被2和3整除，所以它会被点两次（一轮是所有数，一轮是所有2的倍数，一轮是所有3的倍数）。但是，如果一个数同时是多个质数的倍数，那么它被点的次数会增加。例如，数字30可以被2、3和5整除，所以它会被点三次（一轮是所有数，一轮是所有2的倍数，一轮是所有3的倍数，一轮是所有5的倍数）。

为了找出所有被点奇数次的编号，我们需要计算每个数的因数个数。一个数的因数个数是奇数，当且仅当这个数是一个完全平方数。这是因为因数总是成对出现的，除了完全平方数，其中一个因数（平方根）只出现一次。

因此，我们可以通过计算1到n中有多少个完全平方数来解决这个问题。一个数( k )是完全平方数当且仅当( \sqrt{k} )是一个整数。所以，我们需要计算( \sqrt{n} )的整数部分。

下面是一个简单的算法步骤：

1. 初始化计数器count为0。
2. 遍历从1到( \sqrt{n} )的整数。
3. 对于每个数i，如果i^2小于或等于n，则增加计数器count。
4. 返回计数器count的值。

在编程实现中，这可以简化为单步计算，因为不需要实际遍历：

import math

def count_prisoners(n):
    return int(math.sqrt(n))

这个函数计算了从1到n中有多少个完全平方数，也就是有多少个死刑犯会被释放。