PAT乙1007.素数对猜想

发表于 | 分类于

题目

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

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

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

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

输入样例：
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
#include <iostream>
#include <cmath>
using namespace std;
//素数 
bool judge(int n){
    int sqr = sqrt(n); //开始写成了sqrt(n)+1，后来二水马说不用加1也可以
    int divider = 2;
    bool result = true;
    while(divider <= sqr){ //这里需要加等于号
        if(n % divider == 0){
            result = false;
            break;
        }
        divider ++;
    }
    return result;
} 

int main(){
    int n;
    cin >> n;
    int cnt = 0;
    if(n==1 || n==2){ //一开始错了一部分,立马想到这里得判断,主要是针对1
        cout << cnt << endl;
    }
    else{
        for(int i=2; i<=n-2; i++){
            if(judge(i) == true && judge(i+2) == true){
                cnt ++; //这里我原本是手动用了i+=2,所以一直错,其实顶多加个i+=1就好了。
            }
        }
        cout << cnt << endl;
    }
    
}

另外，二水马的建议是，for循环里面不要手动i++之类的，容易出错。如果要手动，可以用while循环。这题还是很简单的，但是我总是有很多小错误。。。