质数ABC

题目分析

题目要求找寻 $n$ 以内的 $3$ 个 质数，并按照式子 $a ^ 2 + b + c ^ 2 <= n$。

那么 $a^2 <= n$，所以 $a <= \sqrt{n}$，也就是说我们只要求 $\sqrt{n}$ 以内所有的质数即可，这个用埃氏筛处理一下，所求的质数个数大约是 $78499$。

然后暴力枚举所有情况就可以了。

AC代码

#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;
}