题解 | #素数对#

我们要找这样的素数对，都为质数，且满足：

现在给定，求以内的素数对。

首先因为都是质数，所以我们先用线性筛把以内的质数都给预处理出来。

观察式子，可以发现，所以我们直接考虑暴力枚举，这时候就变成了在以内找到两个数的和等于一个的经典问题，我们可以使用一个来优化这个匹配，也就是再枚举，然后检查在中是否存在就好。

时间复杂度：我们用表示以内的质数个数，那么时间复杂度就为，当时，大概是，但是因为有很多剪枝，实际复杂度远小于这个，而且这个做法很明显是对的。

#include <iostream>
#include <vector>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
vector<int> primes;
bool vis[N];
void init() {
    vis[0] = vis[1] = 1;
    for (int i = 2; i < N; i++) {
        if (!vis[i]) primes.push_back(i);
        for (int p : primes) {
            if (i * p >= N) break;
            vis[i * p] = 1;
            if (i % p == 0) break;
        }
    }
}
int main() {
    init();
    int n;
    cin >> n;
    //枚举c，因为a+b<=1e6,故c<=1e3
    int up = sqrt(2 * n);
    set<int> se;
    for(int p:primes){
        if(p>n) break;
        se.insert(p);
    }
    int ans=0;
    for(int c=2;c<=up;c++){
        if(!vis[c]){
            for(int p:primes){
                if(p>c*c||p>n) break;
                if(se.count(c*c-p)){
                    // cout << "a:" << p << ",b:" << c*c-p << ",c:" << c << endl;
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}
// 64 位输出请用 printf("%lld")