让我们定义d​n​​ 为：d​n=p​n+1−p​n​​ ，其中p​i是第i个素数。显然有d​​ =1，且n>1有d​n是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。 现给定任意正整数N(<10^5)，请计算不超过N的满足猜想的素数对的个数。

输入格式

输入在一行给出正整数N。

输出格式

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例

20

输出样例

4

“相邻且差为2的素数”即x和x+2都为素数时，x和x+2是题目所求的素数对 最小的一对素数对是3和5，所以在判断x是否为素数时，可以直接从3开始

值得注意的是,判断素数并不需要一直从2除到x-1，看是否会整除 只需判断到√x即可 如果一直到x-1，检测点5会因为超时而不通过

#include<iostream> #include<cmath> using namespace std; bool su(int n) { for (int i = 2; i <= sqrt(n); i++) { if (n % i == 0) return false; } return true; } int main() { int n,m=0; cin >> n; for (int i = 3; i + 2 <= n; i++) { if (su(i) && su(i + 2)) m++; } cout << m<<endl; }