http://acm.hdu.edu.cn/showproblem.php?pid=2866

题意:给一个 N 看能不能找到一个质数 p 使得 n 2 ( n + p ) = m 3

假设 n + p = x 3 , n = y 3 ,那这样多爽,方程就变成了 ( x 3 ) 2 y 3 = m 3 ,那肯定能使得方程成立,这样只用看 p 是不是质数就行了

再来看怎么求 p
p = x 3 y 3 = ( x y ) ( x 2 + x y + y 2 )
然后因为 p 是质数,所以分解成的这两个因式其中必然有一个是 1 ,很显然 ( x y ) = 1 ,所以 x = y + 1 ,所以 p = 3 y 2 + 3 y + 1

然后枚举 y 判断 p 是不是质数就行了,是就加入答案里面

#include"bits/stdc++.h"
using namespace std;
const int maxn=1e6+5;
vector<int> prime;
bool vis[maxn];
void PRIME(int n)
{
    memset(vis,1,sizeof(vis));
    for(int i=2;i<=n;i++)
    {
        if(vis[i])prime.push_back(i);
        for(int j=0;j<prime.size()&&i*prime[j]<=n;j++)
        {
            vis[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
}
int main()
{
    PRIME(1000000);
    vector<int>ans;
    for(long long i=1;;i++)
    {
        long long tp=(long long)(3*i*i+3*i+1);
        if(tp>1000000)break;
        if(vis[tp])ans.push_back(tp);
    }
    int N;
    while(cin>>N)
    {
        int t=upper_bound(ans.begin(),ans.end(),N)-ans.begin();
        if(t)cout<<t<<endl;
        else cout<<"No Special Prime!"<<endl;
    }
}