题目分析

本题主要解决两个点，一是如何判断一个数是否为素数；二是如何统计相邻素数之差等于2的对数。

素数的定义为除1和自身意外再没有其他因子的正整数。一般的想法是，用一个for循环内嵌if条件语句，结合一个开关量来完成这一判断。值得注意的是，这里for语句中的跳出条件最好使用平方小于而非简单的小于。前者是O(√n)的时间复杂度，后者是O(n)的时间复杂度。由于题目要求N最大为10⁵，因此O(n)有出现时间超出要求的可能。

统计相邻差为2的素数对个数也有两种选择。一是将所有小于等于N的素数存于一个预设数组中，然后再一遍遍历计算相邻差值并统计。这种方法的缺点是占用了较大的空间。一个更精简的办法是采用一个int pre变量来存储上一步确认为素数的数，将其与当前确认的素数作差并更新pre的值。这种思想在很多优化算法中都有影子，应着重关注。

代码

#include "iostream"
#define maxn 100005
using namespace std;

bool is_prime(int n){
    for(int i=2; i*i<=n; ++i){
        if(n%i == 0) 
            return false;
    }
    return true;
}

int main(){
    int n, pre = 1, cnt = 0;
    cin >> n;
    for(int i=1; i<=n; i++){
        if(is_prime(i)){
            if(i-pre == 2)
                cnt++;
            pre = i;
        }
    }
    cout << cnt;
    return 0;
}

踩坑指南

有了上面的代码框架后，我提交的代码总是部分正确，最后一组数据一直无法通过判题。后来我发现是main函数中for语句中的循环变量出现了问题。i的取值应该从1开始取，即使pre已经初始化为最小素数1，也不能将i从2开始取，具体为什么我还没有搞清楚。