#include
using namespace std;
int n,a[1000005],s;
void check(int x)
{
    a[1]=1;
    for(int i=2;i*i<=x;i++)
        if(a[i]==0)
            for(int j=i*i;j<=x;j+=i)
                a[j]=1;
}
int main()
{
//	freopen("rsss.in","r",stdin);
//	freopen("arsss.out","w",stdout);
    cin>>n;
    check(n);
    for(int i=1;i<n;i++){
        if(a[i]==0){
            for(int j=i+1;j<=i+2;j++){
                if(a[j]==0&&j<=n)
                    s++;
            }
        }	
    }
    cout<<s;
    return 0;
}

问题描述：

桐桐把大小之差不超过2的两个素数称为一对孪生素数，如2和3、3和5、17和19等等。请你帮助桐桐统计一下，在不大于自然数N的素数中，孪生素数的对数。

思路1（90）

很多人第一时间会想到枚举+素数。 从1枚举到n，每次判下素数，并与前一个判断是否差值小于2。 这确实是一个正常的方法。

#include <bits/stdc++.h>
using namespace std;
bool p[20000000];
int a[2000000];
bool ss(int n)//判断素数的函数 
{
	if(n<2)return false;
	if(n==2)return true;//特判 
	for(int i=2; i<=sqrt(n); i++)  
		if(n%i==0)
	  		return false;
	return true;
}
int main() {
	int n;
	cin>>n;
	int x=-1,sum=0;//初值 
	for(int i=2; i<=n; i++)  
	{
		if(ss(i)) //如果是个素数 
		  {
		  	 if(i-x<=2) sum++;//是与前一个素数是孪生素数，计数器+1 
		  	 x=i;//下次的“前一个数” 
		  }
	}
	cout<<sum;
	return 0;
}

为什么会只有90分呢？；

当n=1000000时，则整个程序的时间复杂度为o（1000000*1000（1000是1000000的平方根）），即o（1000000000），肯定会爆。

思路二（正解）

既然判断素数不行，那我们换一种思路，用埃氏筛来筛素数，提前将素数找出。 代码如下

#include <bits/stdc++.h>
using namespace std;
bool p[20000000];
int a[2000000];
void ss (int n) {//筛法求素数
	p[1]=1;
	for(int i=2; i*i<=n; i++)
		if(!p[i])
			for(int j=2; i*j<=n; j++)
				p[i*j]=1;
	return ;
}
int main() {
	int n;
	cin>>n;
	ss(n); 
	int x=-1,sum=0;//初值 
	for(int i=2; i<=n; i++)  
	{
		if(!p[i]) //如果是个素数 
		  {
		  	 if(i-x<=2) sum++;//是与前一个素数是孪生素数，计数器+1 
		  	 x=i;//下次的“前一个数” 
		  }
	}
	cout<<sum;
	return 0;
}

再看一下时间复杂度，o(n)，可以通过，则本题AC。

思路三（与思路二复杂度一样）

将素数筛好后，我们用将其保存到数组中 下面出示代码：

#include <bits/stdc++.h>
using namespace std;
bool p[20000000];
int a[2000000];
void ss (int n)//筛法求素数 
{
	p[1]=1;
	for(int i=2; i*i<=n; i++)
		if(!p[i])
			for(int j=2; i*j<=n; j++)
				p[i*j]=1;
	return ;
}
int main() {
	int n;
	cin>>n;
	ss(n);
	int s=0,sum=0;
	for(int i=1; i<=n; i++)  if(!p[i]) a[++s]=i;//保存
	for(int i=2; i<=s; i++)  if(a[i]-a[i-1]<=2) sum++;//如果当前素数和前一个素数之差小于等于2，答案+1 
	cout<<sum;
	return 0;
}

#include <bits/stdc++.h>
using namespace std; 
long long s,n;
int ss(int k)
{
	if(k<=1) return false;
	for(int i=2;i*i<=k;i++) 
	{
		if(k%i==0) return false;
	}
    return true;
}
int main() 
{
	cin>>n;
    for(int i=3;i<=n;i++)
    {
    	if(ss(i))
		{
    		if(ss(i-1)) s++;
    		if(ss(i-2)) s++;
		}
	}
	cout<<s;
    return 0; 
}

#include <bits/stdc++.h>
using namespace std;
int n,ans;
bool prime (int n) {//判断素数的函数
    if (n<2) return false;
    for (int i=2;i*i<=n;i++) 
      if (n%i==0) return false;
    return true;
}
int main() {
    cin>>n;
    for (int i=2;i<=n-2;i++) {//注意：这里指的是不超过n，如果超出了n（如n-1和n+1都是素数），则不是一对题目需要求出来的孪生素数。（80WA）
        if (prime (i)) {//当前的数字是素数时
            if (prime (i+1) || prime (i+2)) ans++;//当i+1或者i+2是素数，则将ans加一
        }
    }
    cout<<ans;//输出答案
    return 0;
}