题解 | #素数三元组#

线性筛+孪生素数

如果你还不知道什么是线性筛，可以先去学一学模板

什么是孪生素数？https://baike.baidu.com/item/%E5%AD%AA%E7%94%9F%E8%B4%A8%E6%95%B0/10399834?fr=ge_ala 在自然数中总存在素数对(p,p+2),所以（2，p，p+2）就是一对三元组。 因为除2以外的素数都是奇数，所以三元组是一定包含2的（奇+偶=奇）

那么这题的做法就是根据素数表找到每一对孪生素数，再对数组进行前缀和处理

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
bool vis[N];
int primes[N];
int cnt = 0;
int a[N];
void get_primes() {
	for (int i = 2; i < N; i++) {
		if (!vis[i]) primes[cnt++] = i;
		for (int j = 0; primes[j] < N / i; j++) {
			vis[primes[j] * i] = 1;
			if (i % primes[j] == 0) break;
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	get_primes();
	for (int i = 0; i < cnt; i++) {
		if (!vis[primes[i] + 2]) a[primes[i] + 2] = 1;
	}
	for (int i = 1; i < N; i++) a[i] += a[i - 1];
	int t; cin >> t;
	while (t--) {
		int n;cin >> n;
		cout << a[n] << "\n";
	}
	return 0;
}