Class - 26 : Task - 2

#include<bits/stdc++.h>
using namespace std;
const int mx=1e7+123;
bool is_prime[mx];
int sum[mx];
int cum_sum[mx];
void cal_prime(int n)
{
    for(int i=3;i<=n;i+=2) is_prime[i]=1;
    is_prime[2]=1;
    for(int i=3;i*i<=n;i+=2)
    {
        if(is_prime[i]==1)
        {
            for(int j=i*i;j<=n;j+=(i+i)) is_prime[j]=0;
        }
    }

}

void sum_cal()
{
    for(int x=1;x<=3200;x++)
    {
        for(int y=1;y<=60;y++)
        {
             int p=(x*x)+(y*y*y*y);
             if(p>1e7) continue;
            if(is_prime[p]==1) sum[p]=1;
        }
    }
}
void cu_sum()
{
    cum_sum[1]=sum[1];
    for(int i=2;i<=1e7;i++)
    {
        cum_sum[i]=cum_sum[i-1]+sum[i];
    }
}
int main()
{
    cal_prime(1e7);
    for(int i=1;i<=1e7;i++) sum[i]=0;
    sum_cal();
    cu_sum();
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cout<<cum_sum[n]<<endl;
    }

}