素数对猜想 (PATB-1007)

题面

让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10^5)，请计算不超过N的满足猜想的素数对的个数。

输入

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

输出

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

样例输入

120

样例输出

14

提示

无

思路

代码

 1const int mxn = 1e5 + 5;
 2int n, m;
 3
 4bool isP[mxn];
 5int prime[mxn];
 6
 7int euler(int n)
 8{
 9    memset(isP, 1, sizeof isP);
10    isP[0] = isP[1] = 0;
11
12    int cnt = 0;
13    for (int i = 2; i <= n; i++)
14    {
15        if (isP[i]) prime[++cnt] = i;
16        for (int j = 1; j <= cnt; j++)
17        {
18            if (i * prime[j] > n) break;
19            isP[i * prime[j]] = 0;
20            if (i % prime[j] == 0) break;
21        }
22    }
23    return cnt;
24}
25
26int a[mxn];
27
28int main()
29{
30    int cnt = euler(N);
31    memset(a, 0, sizeof a);
32    for (int i = 3; i <= N; i++)
33    {
34        if (isP[i] && isP[i - 2])
35            a[i] = a[i - 1] + 1;
36        else
37            a[i] = a[i - 1];
38    }
39    scanf("%d", &n);
40    printf("%d\n", a[n]);
41    return 0;
42}