【题解】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;
}
_/_/_/_/_/ EOF _/_/_/_/_/