原文链接：http://www.cnblogs.com/DrunBee/archive/2012/09/05/2672546.html
题意：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
我们可以由n^(1/p)，知道指数为p的有多少个数。
通过观察，可以发现若一个数可以表示成x^(k*t)，则可以表示成(x^k)^t。因此指数必然为素数。
枚举素数便可以得到指数为p的个数，但是可能出现重复，例如：x^3=y^5，其中x=t^5，y=t^3。
运用容斥原理，设a[i]表示指数为第i个素数的个数，那么答案等于满足一个的，减去两个的，加上三个的……
由于2^60>10^18，2*3*5*7>60，所以只要枚举到三即可。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#define EPS 1e-8
#define MAXN 65
typedef long long LL;
using namespace std;
bool p[MAXN];
vector<int> prime;
void Init()
{
int i, j;
memset(p, true, sizeof(p));
for (i = ; i < ; i++)
{
if (p[i])
{
for (j = i * i; j < MAXN; j += i)
p[j] = false;
}
}
prime.clear();
for (i = ; i < MAXN; i++)
{
if (p[i])
prime.push_back(i);
}
}
int main()
{
LL n, tmp;
int i, j, k, ans;
Init();
while (~scanf("%I64d", &n))
{
ans = ;
for (i = ; i < (int) prime.size(); i++)
{
tmp = (LL) (pow((double) n, 1.0 / prime[i]) + EPS);
if (tmp == )
break;
ans += tmp - ;
}
for (i = ; i < (int) prime.size(); i++)
{
for (j = i + ; j < (int) prime.size(); j++)
{
tmp = (LL) (pow((double) n, 1.0 / (prime[i] * prime[j])) + EPS);
if (tmp == )
break;
ans -= tmp - ;
}
}
for (i = ; i < (int) prime.size(); i++)
{
for (j = i + ; j < (int) prime.size(); j++)
{
for (k = j + ; k < (int) prime.size(); k++)
{
tmp = (LL) (pow((double) n,
1.0 / (prime[i] * prime[j] * prime[k])) + EPS);
if (tmp == )
break;
ans += tmp - ;
}
}
}
printf("%d\n", ans);
}
return ;
}