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

题目描述：定义d(n)为：d(n)=p(n+1)-p(n)，其中p(i)是第i个素数。显然有d(1)=1，对于n>1有d(n)是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

要求：给定任意正整数n（<10^5），请计算不超过n的满足“素数对猜想”想要的素数对个数。

回答：题目就是让我们求出不超过n的满足条件的素数对的数量。

朴素算法是枚举n以内的所有偶数，再判断它们是否都能表示成两个素数之和，复杂度为O(n^2)。优化算法是先预处理出n以内的素数，再扫描一遍这些素数，统计它们与它们后面的素数之间是否差为2，复杂度为O(nloglogn)。

具体实现可参考如下python代码：