题解：SP4164 HS08PAUL - A conjecture of Paul Erdős

· · 题解

题解：SP4164 HS08PAUL - A conjecture of Paul Erdős

思路分析

我们先用筛法筛出 1 \sim 10^6 所有的质数，则用一个数组将原数对应位置标记为 1。

然后，用前缀和：sum[i]=sum_[i-1]，即可求出 1 \sim i 中所有的满足题目所述的素数个数。

最后，输入时，仅仅只需要输出 sum_n 即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[10000005];
int sum[10000005];
vector<int> prime;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    for(int i=2;i<=10000000;i++){
        if(vis[i]==0){
            for(int j=2;j<=10000000/i;j++)vis[min(i*j,10000000ll)]=1;
            prime.push_back(i);
        }
    }
    for(int x=1;x*x*x*x<=10000000;x++)
        for(int y=1;y*y<=10000000;y++)
            if(vis[min(x*x*x*x+y*y,10000000ll)]==0)
                sum[min(x*x*x*x+y*y,10000000ll)]=1;
    for(int i=1;i<=10000000;i++)sum[i]+=sum[i-1];
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<sum[n]<<"\n";
    }
    return 0;
}