Spoj Solution:CUBEFR - Cube Free Numbers

#include <bits/stdc++.h>
#define pb push_back
#define MAX 1000006
#define lim 1000006
using namespace std;
typedef long long ll;

vector<int>prime;
bool mark[MAX];
void sieve()
{
    for(int i=3; i<=sqrt(MAX); i+=2)
    {
        if(!mark[i]) for(int j=i*i; j<MAX; j+=i) mark[j]=true;
    }
    prime.pb(2);
    for(int i=3; i<MAX; i+=2) if(!mark[i]) prime.pb(i);
}
bool chk[lim];
int y[lim];
void cube_sieve()
{
    for(int i=0; prime[i]*prime[i]*prime[i]<lim; i++)
    {
        int n=prime[i]*prime[i]*prime[i];
        for(int j=1; n*j<lim; j++) chk[n*j]=true;

    }
    for(int i=1,k=1; i<lim; i++) if(!chk[i]) y[i]=k++;

}
int main()
{
    // freopen("input.txt","r",stdin);

    sieve();
    cube_sieve();
    int test;
    scanf("%d",&test);
    for(int cas=1; cas<=test; cas++)
    {
        int n;
        scanf("%d",&n);
        printf("Case %d: ",cas);
        if(chk[n]) puts("Not Cube Free");
        else printf("%d\n",y[n]);

    }


    return 0;
}