我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。
题目
让我们定义 为：
，其中
是第
个素数。显然有
，且对于
有
是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N( )，请计算不超过
N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
4
思路
初始化：100个素数里初始化便写入前两个2，3，从4开始验证，这样不影响边界情况（N=5之前没有孪生素数），避免了2这样没有更小的素数可供验证的情况，并且进入循环即可开始验证孪生素数。
结果参考：
| N | 孪生素数对数 |
|---|---|
| 1~4 | 0 |
| 20 | 4 |
| 100 | 8 |
| 1000 | 35 |
| 10000 | 205 |
| 100000 | 1224 |
代码
最新代码@github，欢迎交流
#include <stdio.h>
int main()
{
int N;
scanf("%d", &N);
/* Record primality of three successive numbers starting from 2, 3, 4 */
int iPrimeMinus2 = 1, iPrimeMinus1 = 1, iPrime;
int primes[100] = {2, 3}; /* Record the prime numbers before sqrt(10^5) */
int twincount = 0; /* Count of twin primes */
int primecount = 2; /* Count of prime numbers */
/* Start from 4 */
for(int i = 4; i <= N; i++)
{
/* Test if i is a prime number */
iPrime = 1;
for(int j = 0; iPrime && primes[j] * primes[j] <= i; j++)
if(i % primes[j] == 0)
iPrime = 0;
/* If i is a prime number, record */
if(iPrime)
{
if(primecount < 100) primes[primecount++] = i;
if(iPrimeMinus2 == 1) twincount++; /* a prime pair found */
}
/* Shift the primality flags to next numbers */
iPrimeMinus2 = iPrimeMinus1;
iPrimeMinus1 = iPrime;
}
printf("%d", twincount);
return 0;
}
