00-自测2. 素数对猜想 (20)

Posted on   |   In   |  

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

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

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

1
2
3
4
输入样例：
20
输出样例：
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
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int element[100001];
int main()
{
    int N = 0;
    cin >> N;
    int position = 0;
    for(int i = 0; i < N; ++i)
    {
        if(pow(i, 2) > N)
        {
            position = i;
            break;
        }
    }
    for(int i = 0; i <= N; ++i)
    {
        element[i] = i;
    }
    for(int i = 2; i < position; ++i)
    {
        if(element[i] != 0)
        {
            for(int j = i + 1; j <= N; ++j)
            {
                if(element[j] != 0 && (element[j] % element[i] == 0))
                {
                    element[j] = 0;
                }
            }
        }
    }
    vector<int> ivec;
    for(int i = 0; i <= N; ++i)
    {
        if(element[i] != 0)
        {
            ivec.push_back(element[i]);
        }
    }
    int countNum = 0;
    for(int i = 0; i < ivec.size() - 1; ++i)
    {
        if(ivec[i+1] - ivec[i] == 2)
        {
            ++countNum;
        }
    }
    cout << countNum << endl;
    return 0 ;
}

第一次提交测试点1没过，一猜就是某个边界没弄好，而且数还不大，然后想来一下，试了7，发现7输出的是1，才知道自己在算的时候，把7漏了，不超过N，是可以包括N的，所以在某些地方加上=就过了。
自己想的方法无非是就是开根号后一个个试，一看这样的题目就是求素数，数学方面的解法肯定有不少比较简单的，百度了一下求素数的方法，看到一个叫厄拉多塞筛法的办法，不难理解，然后实现了一下，就采用它了。主要还是PAT这一题测试的数据量不大，不然我也得跪。
测试结果：

测试点 结果 用时(ms) 内存(kB) 得分/满分
0 答案正确 1 180 10/10
1 答案正确 1 308 2/2
2 答案正确 1 256 2/2
3 答案正确 1 256 2/2
4 答案正确 1 308 2/2
5 答案正确 16 820 2/2