<题目链接>
题目大意：
Ignatius 喜欢收集蝴蝶标本和邮票，但是Eddy的爱好很特别，他对数字比较感兴趣，他曾经一度沉迷于素数，而现在他对于一些新的特殊数比较有兴趣。
这些特殊数是这样的：这些数都能表示成M^K，M和K是正整数且K>1。
正当他再度沉迷的时候，他发现不知道什么时候才能知道这样的数字的数量，因此他又求助于你这位聪明的程序员，请你帮他用程序解决这个问题。
为了简化，问题是这样的：给你一个正整数N，确定在1到N之间有多少个可以表示成M^K（K>1)的数。
解题分析：
解决本题需要先知道一个结论：在一个区间[1,n]中，能被开平方的数一共有 
个。同理，在区间[1,n]中，能被开立方的数一共有
个.....更一般的，能够被开k次方的数一共会有
个数。
因为$k$是幂数，所以$k$在本题的范围很小，考虑枚举$k$。对于$k$，假设$k$是合数，那么k一定能够被分解为若干个质数相乘的形式，而这些质数在前面枚举的时候就会被考虑到，所以我们只需要枚举k为质数的情况。而即使是2作为底数，$2^{60}$就已经大于$10^{18}$，所以我们只需要考虑k为小于60的质数的情况。
k为所有质数的情况中，有一些情况会被重复计算，这个时候就需要用到容斥原理了。因为2*3*5>60，所以我们只需要考虑3个质数相互组合容斥的情况。
#include <bits/stdc++.h>
using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++)
typedef long long ll; const int prime[]={ ,,,,,,,,,,,,,,,, };
ll n; inline ll solve(ll k){ //利用结论计算这个区间内能被开(1/k)次方的数的个数(1除外)
return pow(n,1.0/k)-;
} int main(){
while(cin>>n){
ll ans1=,ans2=,ans3=;
rep(i,,)ans1+=solve(prime[i]);
rep(i,,) rep(j,i+,){
ans2+=solve(prime[i]*prime[j]);
}
rep(i,,) rep(j,i+,) rep(k,j+,){
ans3+=solve(prime[i]*prime[j]*prime[k]);
}
cout<<ans1+ans3-ans2+<<endl;
}
}