#include <bits/stdc++.h> using namespace std; typedef unsigned long long ll; const ll N = 1e6 + 10; bitset<N> Prime; vector<ll> v; void __init() { for(ll i=2;i<=N/i;i++) { if (Prime[i])continue; for(ll j=i*2;j<=N;j+=i) { Prime[j] = true; } } for(ll i=2;i<=N;i++) { if(Prime[i])continue; v.push_back(i); } } int main() { __init(); //cout << v.size() << endl; ll n; cin >> n; int ans = 0; for(int i=0;i<v.size();i++) { ll a = v[i] * v[i]; if (a > n)break; for(int j=i+1;j<v.size();j++) { ll b = v[j]; if (a * b > n)break; for(int k=j+1;k<v.size();k++) { ll c = v[k] * v[k]; if (a * b * c > n)break; ans++; } } } cout << ans << endl; return 0; }

质数ABC 题目分析 题目要求找寻 nnn 以内的 333 个 质数，并按照式子 a2+b+c2<=na ^ 2 + b + c ^ 2 <= na2+b+c2<=n。 那么 a2<=na^2 <= na2<=n，所以 a<=na <= \sqrt{n}a<=n ，也就是说我们只要求 n\sqrt{n}n 以内所有的质数即可，这个用埃氏筛处理一下，所求的质数个数大约是 784997849978499。 然后暴力枚举所有情况就可以了。 AC代码

a,ba,ba,b 暴力for，然后我们注意到通过 a,ba,ba,b 可以求到 ccc 的范围，二分就行 时间复杂度：O((n3)2log⁡n)O((\sqrt[3] n)^2\log n)O((3n )2logn).