【题解】PATB-1007 素数对猜想

发表于 分类于 ， ， ， 本文字数： 194 阅读时长 ≈ 1 分钟
PATB-1007 素数对猜想 类型 水题 欧拉筛

素数对猜想 (PATB-1007)

题面

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

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

输入

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

输出

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

样例输入

1
20

样例输出

1
4

提示

无

思路

代码

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
36
37
38
39
40
41
42
const int mxn = 1e5 + 5;
int n, m;

bool isP[mxn];
int prime[mxn];

int euler(int n)
{
    memset(isP, 1, sizeof isP);
    isP[0] = isP[1] = 0;

    int cnt = 0;
    for (int i = 2; i <= n; i++)
    {
        if (isP[i]) prime[++cnt] = i;
        for (int j = 1; j <= cnt; j++)
        {
            if (i * prime[j] > n) break;
            isP[i * prime[j]] = 0;
            if (i % prime[j] == 0) break;
        }
    }
    return cnt;
}

int a[mxn];

int main()
{
    int cnt = euler(N);
    memset(a, 0, sizeof a);
    for (int i = 3; i <= N; i++)
    {
        if (isP[i] && isP[i - 2])
            a[i] = a[i - 1] + 1;
        else
            a[i] = a[i - 1];
    }
    scanf("%d", &n);
    printf("%d\n", a[n]);
    return 0;
}