应该注意筛质数的数据范围

将Shuaishuai数定义为一个数，它是一个质数的平方、立方和四次方的和。

前四个Shuaishuai数是：

在[1，n]范围内有多少个Shuaishuai数？（1<=n<=50 000 000）

输入描述：

输入将由一个整数n组成。

输出描述：

您应该输出[1...n]范围内有多少个Shuaishuai数。

#include<bits/stdc++.h>
using namespace std;

const int N = 84,K = 5e7;
int p[N],cnt,ans;
bool st[N];    //84^2+84^3+84^4 = 50386896

void init(){
    for(int i=2; i<=N; i++){
        if(!st[i])    p[cnt++] = i;
        for(int j=0; p[j]<=N/i; j++){
            st[p[j]*i] = true;
            if(i%p[j]==0)    break;
        }
    }
}
int main()
{
//     int a = 84*84;
//     cout<<a+a*84+a*a;
    int n;    cin>>n;
    init();

    for(int i=0; i<cnt; i++){
        int a = p[i]*p[i];
        if(a>=n)    continue;
        for(int j=0; j<cnt; j++){
             int b = p[j]*p[j]*p[j];
            if(a+b>=n)    continue;
            for(int k=0; k<cnt; k++){
                int c = p[k]*p[k]*p[k]*p[k];
                if(a+b+c<=n)    ans++;
            }
        }
    }
    cout<<ans;
        
    return 0;
}

一开始误以为一个质数的平方、立方和四次方的和是最大的，即a^2 + b^3 + c^4中a、b、c取同一个数。

所以通过84^2+84^3+84^4 = 50386896以为质数存到八十多就够了。

实际上也可以一个很小的数的平方加上大数的立方或四次方。因此质数应该重新找出可能的最大质数。

然后又通过150^4 = 506,250,000认为最大到150就够了，实际上还是错误的。

对于题目要求a^2 + b^3 + c^4 <= 50 000 000，应该求出a、b、c所有可能取值的质数，所以应该从a入手，因此最大质数应该接近sqrt(50 000 000)。

下面是修改后的正确解法：

#include<bits/stdc++.h>
using namespace std;
 
//sqrt(50 000 000) = 7071
const int N = 7072,K = 5e7;    //150^4 = 506,250,000
vector<int> p;
bool st[N];    //84^2+84^3+84^4 = 50386896
unordered_set<int> S;
 
void init(int n){
    for(int i=2; i<=n; i++){
        if(!st[i])    p.push_back(i);
        for(int j=0; p[j]<=n/i; j++){
            st[p[j]*i] = true;
            if(i%p[j]==0)    break;
        }
    }
}
int main()
{
//     int a = 84*84;
//     cout<<a+a*84+a*a;
    int n;    cin>>n;
    init(sqrt(n));
    int cnt = p.size();
    for(int i=0; i<cnt; i++){
        int a = pow(p[i],2);
        if(a>=n)    break;
        for(int j=0; j<cnt; j++){
             int b = pow(p[j],3);
            if(a+b>=n)    break;
            for(int k=0; k<cnt; k++){
                int c = pow(p[k],4);
                if(a+b+c>n)    break;
                S.insert(a+b+c);
            }
        }
    }
    cout<<S.size();
         
    return 0;
}