D-有趣的数字

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述 

最近TreeDream沉迷于数字游戏中，发现了一种有趣的数字，有趣的数字定义如下：

给定一组n个数，a[1],a[2],a[3],...,a[n], 初始全为0，现在，在这组数上进行x操作；

x 操作定义如下：

x从1~n依次增加，每次把x的下标的倍数的数进行反转，0变成1,1变成0，操作完后，如果a[i]为0，那么i则是有趣的数。

现在对于给定的n（n<=1e15），求这时候有趣的数的个数。

例如：

n = 3

x = 1 时 ：a[1] = 1, a[2] = 1, a[3] = 1;

x = 2 时 ：a[1] = 1, a[2] = 0, a[3] = 1;

x = 3 时 ：a[1] = 1, a[2] = 0, a[3] = 0;

此时，3个数中，有两个数为0，故有趣的数的个数为2；

输入描述:

多组样例，每个样例占一行，每一行输入一个数n，表示有n个数。（n<=1e15）

输出描述:

每个样例输出一行，一行输出一个数，表示有趣的数的个数。

示例1

输入

3

输出

2

一看就感觉是找规律题，先手算出前21多对应的值，跟平方数的个数有关，平方数个数跟sqrt(n)有关，最后就几行代码……

参考网站

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    while(scanf("%lld",&n)==1)
    {
        long long ans=n-(int)sqrt(n);
        printf("%lld\n",ans);
    }
    return 0;
}