div9 nerdarena

/// O solutie care verifica toate patratele perfecte pana la n ia TLE
#include <fstream>
using namespace std;
ifstream cin("9div.in");
ofstream cout("9div.out");
// Numarul nostru poate veni in doua forme :
// a) x^8, unde x este prim
// b) x^2*y^2, unde x, y sunt prime si y>x
long long primes[20000], p;
bool isPrime(int x)
{
    if(x<2) return false;
    if(x==2||x==3) return true;
    if(x%2==0||x%3==0) return false;
    for(int i = 5;i*i<=x;i+=6)
        if(x%i==0||x%(i+2)==0) return false;
    return true;
}
void genPrimes()
{
    for(int i = 1;i<=31623;i++) // sqrt(1e9)
        if(isPrime(i))
            primes[++p] = i;
}
long long exp(long long x, long long p)
{
    long long sol = 1;
    while(p)
    {
        if(p%2==1)
            sol = sol * x;
        x = x * x;
        p/=2;
    }
    return sol;
}
int main()
{
    genPrimes();
   // cout << p;
    long long n, nr = 1, sol = 0;
    cin >> n;
    for(int i = 1;i<=p&&primes[i]*primes[i]*primes[i]*primes[i]<=n;i++)
    {
         for(int j = i+1;j<=p && primes[j]*primes[j]*primes[i]*primes[i] <= n;j++)
         {
            sol++;
            //cout << primes[i] * primes[i] * primes[j]*primes[j] << ' ';
         }
    }
    while(exp(primes[nr],8)<=n)
        sol++,nr++;
    //cout << p;
    cout << sol << '\n';
    return 0;
}