Give you a prime number p, if you could find some natural number (0 is not inclusive) n and m, satisfy the following expression: 
  

D - Special Prime

 HDU - 2866 
We call this p a “Special Prime”. 
AekdyCoin want you to tell him the number of the “Special Prime” that no larger than L. 
For example: 
  If L =20 
1^3 + 7*1^2 = 2^3 
8^3 + 19*8^2 = 12^3 
That is to say the prime number 7, 19 are two “Special Primes”. 

Input

The input consists of several test cases. 
Every case has only one integer indicating L.(1<=L<=10^6) 

Output

For each case, you should output a single line indicate the number of “Special Prime” that no larger than L. If you can’t find such “Special Prime”, just output “No Special Prime!”

Sample Input

7
777

Sample Output

1
10

题意 求小于l的满足以上式子的 数

题解 自己推导一下或者找一下规律会发现 p=i+1的三次方-i的三次方 并且 p得是素数

自己打了半天的表各种wa。。。后来发现0的时候要输出一句话！！！坑

其实发现别人不打表直接暴力也能过，估计样例不多

打表我用的埃筛+前缀和 到时候直接输出就行

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PI acos(-1.0)
#define Max INT_MAX
#define Min INT_MIN
#define eps 1e-8
#define FRE freopen("a.txt","r",stdin)
#define maxn 1000000+5
typedef long long int ll;
ll quick_pow(ll a,ll b)
{
    ll  ans=1,base=a;
    while(b!=0){
        if(b&1!=0)
            ans*=base;
        base*=base;
        b>>=1;
    }
    return ans;
}
int vis[maxn];
void init1()//埃筛
{
    int m=sqrt(maxn+0.5);
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=m;i++)
    {
        if(!vis[i])
        for(int j=i*i;j<=maxn;j+=i)
        {
            vis[j]=1;
        }
    }
}
int flag[maxn],sum[maxn];
void init2 (){//打表
    memset(flag,0,sizeof(flag));
    memset(sum,0,sizeof(sum));
    for(int i=1;i<800;i++){
        int p=quick_pow(i+1,3)-quick_pow(i,3);
        if(p>=1000000)break;
        if(!vis[p])
        flag[p]=1;
    }
    sum[0]=0;
    for(int i=1;i<1000000+5;i++){
        if(flag[i])sum[i]=sum[i-1]+1;
        else sum[i]=sum[i-1];
    }

}
int main(){
    init1();
    init2();
    int n;
   // cout<<flag[7]<<endl;
    while(scanf("%d",&n)!=EOF){
        int ans=sum[n];
        if(ans==0)printf("No Special Prime!\n");
        else 
        printf("%d\n",sum[n]);
    }
    return 0;
}