<>

题目大意：

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 
     
      using namespace std;#define rep(i,s,t) for(int i=s;i<=t;i++)typedef long long ll;const int prime[]={ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59 };ll n;inline ll solve(ll k){     //利用结论计算这个区间内能被开(1/k)次方的数的个数(1除外)    return pow(n,1.0/k)-1;     }int main(){    while(cin>>n){        ll ans1=0,ans2=0,ans3=0;        rep(i,0,16)ans1+=solve(prime[i]);        rep(i,0,16) rep(j,i+1,16){            ans2+=solve(prime[i]*prime[j]);        }        rep(i,0,16) rep(j,i+1,16) rep(k,j+1,16){            ans3+=solve(prime[i]*prime[j]*prime[k]);        }        cout<
      
       <