题解 | 素数对

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define INF 2e18
#define ull unsigned long long
#define pq priority_queue<int>
const int mod = 1000000007;
const int N = 5e5 + 5;

int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

int days[] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };

//快速幂
inline int ksm(int a, int b)
{
	int mod = 1000000007;
	int ans = 1;
	a %= mod;
	while (b)
	{
		if (b & 1)ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans % mod;
}

bool vis[N];
vector<int>s;

void solve()
{
	int n; cin >> n;
	vis[0] = vis[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!vis[i])s.push_back(i);
		for (int j = 0; j < s.size() && i * s[j] <= n; j++)
		{
			vis[i * s[j]] = 1;
			if (i % s[j] == 0)break;
		}
	}
	vector<int>m;//合法的c的平方
	for (auto x : s)
	{
		if (x * x <= n * 2)
			m.push_back(x * x);
		else
			break;
	}
	int ans = 0;
	for (auto c : m)
	{
		for (auto a : s)
		{
			if (a >= c)continue;
			if (c - a < 2 || c - a > n)continue;
			if (!vis[c - a])ans++;
		}
	}
	cout << ans << endl;
}

signed main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}