题目

让我们定义 $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的满足猜想的素数对的个数。

输入样例:

1

20

输出样例:

1

4

思路

初始化：100个素数里初始化便写入前两个2，3，从4开始验证，这样不影响边界情况（N=5之前没有孪生素数），避免了2这样没有更小的素数可供验证的情况，并且进入循环即可开始验证孪生素数。

结果参考：

N 孪生素数对数
1~4 0
20 4
100 8
1000 35
10000 205
100000 1224

代码

Github最新代码，欢迎交流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#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;
}