PAT乙级1007

Posted on | | Visitors:
Words count in article: 823 字 | Reading time ≈ 4 分

题目链接

https://pintia.cn/problem-sets/994805260223102976/problems/994805318855278592

题解一

根据题意，素数对有两个特点：差为2、相邻，所以我们可以从3开始枚举每一对数字，然后再判断它们两个是不是素数。

这道题刚开始还是有一个点超时（TLE）了，主要原因有三点：

  1. 枚举方法太low，没有利用偶数不可能是素数这一性质。（题解一已处理）

    我刚开始是枚举的是3,5、4,6、……；后来改成了3,5、5,7、……

  2. 判断素数方法太low，用sqrt较好，当然也有更快的方法。（题解一已处理）

  3. for循环中可能重复判断5是不是素数（让我想起来了动态规划..…），增加了时间复杂度（题解一未处理，在题解二中处理）

在网上查题解发现我在判断素数的时候也忘记了处理1不是素数和2是素数的情况。

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
// PAT BasicLevel 1007
// https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num);

int main()
{
    // 获取用户输入的数字
    int N=0;
    cin >> N;

    // 判断素数对的个数
    int count=0;
    for(int i=3;i+2<=N;i+=2){   // 偶数一定不是素数
        if(isPrime(i)&&isPrime(i+2)){
            count++;
        }
    }

    // 输出结果
    cout << count;

    //system("pause");
    return 0;
}

// 判断是否为素数
bool isPrime(int num)
{
    // 并没有处理num为2的情况

    // 用这种方法找素数找的比较快，相当于i<sqrt(num)，但这样精度可能损失，导致错误
    for (int i = 2; i*i <= num; i++){
        if (num%i==0)
            return false;
    }

    // 边界条件，1不是素数
    return num == 1?false:true;
}

题解二

针对题解一中重复判断5是否为素数的问题，我们至少有两种方法解决：

  1. 建一个数组存储所有素数
  2. 用一个变量存储上一个素数且不断更新

网上搜到的题解有方法一，也有方法二，这里采用后者。

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
56
57
58
59
// PAT BasicLevel 1007
// https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

#include <iostream>
#include <cmath>
using namespace std;

bool isPrime(int num);

int main()
{
    // 获取用户输入的数字
    int N=0;
    cin >> N;

    // 素数对的个数
    int count=0;

    // 上一个素数
    int lastPrime=2;    

    // 计算素数对个数
    for(int i=3;i<=N;i+=2){   // 偶数除了2一定不是素数
        // 找到新的素数
        if(isPrime(i)){
            
            // 判断是否为素数对
            if(i-lastPrime==2){ //两个素数之差为2
                count++;    // 计数
            }

            // 更新上一个素数
            lastPrime=i;
        }
    }

    // 输出结果
    cout << count;

    //system("pause");
    return 0;
}

// 判断是否为素数
bool isPrime(int num)
{
    // 1不是素数
    if(num<=1)
        return false;

    // 用这种方法找素数找的比较快，相当于i<sqrt(num)，但这样精度可能损失，导致错误
    for (int i = 2; i*i <= num; i++){
        if (num%i==0)
            return false;
    }

    return true;
    
}

作者：@臭咸鱼

转载请注明出处：https://chouxianyu.github.io

欢迎讨论和交流!