#include <stdio.h>
int prime[1000001];
void ajs(){
    for(int i=2;i<1000002;i++){
        prime[i]=1;
    }
    for(int i=2;i<=1000;i++){
        if(prime[i]){
            for(int j=i*i;j<1000001;j+=i){
                prime[j]=0;
            }
        }
    }
}
int main(){
    ajs();
    int n;
    scanf("%d",&n);
    while(n--){
        int m,cnt=0;
        scanf("%d",&m);
        for(int i=2;i+2<=m;i++){
            if((prime[i]==1&&prime[i+1]==1)||(prime[i]==1&&prime[i+2]==1)){
                cnt++;
            }
        }
        if(m==3)printf("1\n");
        else printf("%d\n",cnt);
    }
    return 0;
}

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <stdbool.h>
using namespace std;
#define int long long
int times = 0;
bool flag[2000005] = {0};
int ans[2000005] = {0};
void ss(){
	for(int i = 0 ; i < 1000005 ; i++){
		flag[i] = {0};
		ans[i] = 0;
	}
	times = 0;
}
void shai(int n) {
	ss();
	flag[0] = flag[1] = 1;
	for (int i = 2 ; i <= n ; i++) {
		if (flag[i] == 0) {
			ans[times++] = i;
			for (int j = i + i ; j <= n ; j += i) {
				flag[j] = 1;
			}
		}
	}
}
signed main() {
	int t;
	cin >> t;
	while (t--) {
		int cnt = 0;
		int a;
		cin >> a;
		shai(a);
		for (int i = 0 ; i < times-1 ; i++) {
			if (ans[i + 1] - ans[i] == 1 || ans[i + 1] - ans[i] == 2) {
				cnt++;
			}
		}
		cout << cnt << '\n';
	}
	return 0;
}

#include<stdio.h>
// #include<iostream>
// using namespace std;
const int x = 1005000;
int flag [x];
void no_prime() {//用埃氏筛，先筛一遍
    flag[1] = 1;
    flag[0] = 1;
    for (int i = 2; i < x; i++) {
        if (flag[i] == 0) {
            for (int j = 2 * i; j < x; j += i) {
                flag[j] = 1;
            }
        }
    }
}
int main() {
    no_prime();
    int n, m;
    scanf("%d",&n);
    while (n--) {
        scanf("%d",&m);
        int arr[1000000] = {0};
        int temp = 0;
        for (int i = 2; i <= m; i++) {
            if (flag[i] == 0) {
                arr[++temp] = i;
            }
        }
        int count = 0; // 注意temp的取值范围，非常容易错
        for (int i = 1; i < temp ; i++) {
            if (arr[i + 1] - arr[i] == 2 || arr[i + 1] - arr[i] == 1) {
                count++;
            }
        }
        printf("%d\n",count);
    }
}

//勉强能过[苦笑][苦笑]

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int t,n,x,sum;
	cin>>t;
	int su[5000000];
	while(t--)
	{
		cin>>n;
		x = 0;
		sum=0;
		//用埃氏筛法筛选出素数
		int aishi[n];
		for(int i=1;i<=n;i++)
		{
			aishi[i]  =1;
		}
		for(int i=2;i<=sqrt(n);i++)
		{
			if(aishi[i])//如果是素数
			{
				for(int j=i*i;j<=n;j+=i)//筛掉倍数
				{
					aishi[j] = 0;
				}
			}
		}
		for(int i=2;i<=n;i++)//将所有素数存到数组里面去，再进行比较
		{
			if(aishi[i])
			{
				su[x++] = i;
			}
		}
		for(int i=1;i<x;i+=2)
		{
			if(su[i+1]-su[i]==1||su[i+1]-su[i]==2)//说明是孪生素数
			{
				sum++;
			}
			if(su[i]-su[i-1]==1||su[i]-su[i-1]==2)
			{
				sum++;
			}
			if(su[i+1]-su[i-1]==2)
			{
				sum++;
			}
		}
		cout<<sum<<endl;
	}
}

#include<stdio.h>
const int N=1e6+5;
int box[N];
void primes()
{
	box[0]=box[1]=1;
	for(int i=2;i<N;i++)
	{
		if(!box[i])
		{
			for(int j=2;j*i<N;j++)
			{
				box[j*i]=1; 
			}
		}
	}
}
int main()
{
	primes();
	int n;
	scanf("%d",&n);
	while(n--)
	{
		int count=0;
		int m;
		scanf("%d",&m);
		for(int i=1;i<=m;i++)
		{
			for(int j=i+1;j<i+3;j++)
			{
                if(j>m)
                break;
				if(!box[i]&&!box[j])
				{
//					printf("%d %d",i,j);
					count++;
				}
			}
		}
		printf("%d\n",count);
	}
}

#include<stdio.h>
int box[1000000+5];
const int N=1e6+5;
void primes(){
     box[0]=1;
     box[1]=1;
     for(int i=2;i<=N;i++){
        if(box[i]==0){
            for(long long j=i;j*i<=N;j++){
                box[i*j]=1;
            }
        }
     }
}
int main()
{
    int n;
    scanf("%d",&n);
    primes();
    while(n--){
        int m;
        scanf("%d",&m);
        int cnt=0;
        for(int i=2;i<=m;i++){
            if((box[i]==0&&box[i-2]==0)||(box[i]==0&&box[i-1]==0)){
                cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}

刚学的热乎的素数筛
```#include<stdio.h>
#include<math.h>
const int n=1e6+5;
int box[1000000];
void primes();
int main()
{
	int t;
	scanf("%d",&t);
	primes();
	box[0]=1;
	box[1]=1;
	while(t--)
	{
		int cnt=0;
		int m;
		scanf("%d",&m);
		for(int i=2;i<=m;i++)
		{
			if((box[i]==0&&box[i-1]==0)||(box[i]==0&&box[i-2]==0))
			{
				cnt++;
			}
		}
		printf("%d\n",cnt);
	}
}

void primes()
{
	for(int i=2;i<=n;i++)
	{
		if(box[i]==0)
		{
			for(int j=i+i;j<=n;j+=i)
			{
				box[j]=1;
			}
		}
	}
}
``````
`````````

素数筛选法： 开一个大数组，下标表示所有1 -- m之间的数。思路是把素数标记为1， 非素数标记为0； 因为偶数肯定不是素数，所以先标记所有偶数为0；还有一种方法是让下标从3开始，每次加2，就避过了偶数， 这样不用管偶数，更加省时。然后就是从3到根号下m之间，只要是素数，它的倍数肯定不是素数，标记为0. 这样，剩下的被标记为1的奇数就是要找的1 -- m之间的所有素数。 另外，总共进行n次测试，在测试之前标记完成，每次测试只要取其结果即可。

int func(int);
int main(void)
{
	int n, m, i, j, num;
	int buf[100000]={0};//注意buf树状数组
	scanf("%d", &n);
 
	j=0;
	buf[j++]=2;
	/*把2到1000000的素数放到数组里*/
	for(i=3; i<1000001; i += 2){
		if(func(i) == 1){
			buf[j++] = i;
		}
	}
 
	while(n--){
		num=0;
		scanf("%d", &m);
		for(i=1; i<=m; i++){
			if(buf[i]>m){
				break;
			}
			if((buf[i]-buf[i-1] == 1) || (buf[i]-buf[i-1] == 2)){
				num++;
			}
		}
 
		printf("%d\n", num);
	}
 
	return 0;
}
 
/*求是否为素数*/
int func(int n)
{	
	if(n<2){
		return -1;
	}
	int i;
	for(i=2; i<=sqrt(n); i++){
		if(n%i==0){
			return 0;
		}
	}
	return 1;
}

$\ \ \ \ \ \ \$一次性统计完所有数字对应的孪生素数对数，这样就不需要每次重新循环统计。

#include <cstdio>

const int MAXN = 1000010;

bool isPrime[MAXN];
int twinPrimes[MAXN];

int fillIsPrime(){
    for(int i = 2; i <= MAXN; i++){
        isPrime[i] = true;
    }
    for(int i = 2; i <= MAXN; i++){
        if(isPrime[i]){
            for(int j = 2 * i; j <= MAXN; j += i){
                isPrime[j] = false;
            }
        }
    }
    return 0;
}

int main(){
    fillIsPrime();
    int n, m, rec = 1;
    scanf("%d", &n);
    twinPrimes[0] = 0;
    twinPrimes[1] = 0;
    twinPrimes[2] = 0;
    for(int i = 3; i <= 1000010; i ++){
        if(isPrime[i] && isPrime[i - 2]){
            rec ++;
        }
        twinPrimes[i] = rec;
    }
    for(int i = 1; i <= n; i ++){
        scanf("%d", &m);
        printf("%d\n", twinPrimes[m]);
    }
    return 0;
}