PAT乙级1099性感素数题解与算法优化

1. PAT乙级1099题目解析与实战攻略

作为一名参加过多次PAT考试的程序员，我清楚地记得1099这道题目给不少考生带来的困扰。这道题看似简单，但暗藏玄机，考察了选手对基础算法的掌握程度和代码实现能力。今天我就带大家彻底拆解这道经典题目，分享我的解题思路和优化技巧。

1.1 题目核心要求分析

PAT乙级1099的完整题目名称是"性感素数"，题目要求我们判断给定的正整数N及其相邻的数N-6或N+6是否都是素数。如果是，则输出"Yes"并打印较小的那个素数；否则找出比N大的最小性感素数对。

这道题主要考察三个核心能力：

1. 素数判断的高效实现
2. 边界条件的全面考虑
3. 算法的时间复杂度控制

在实际考试中，很多同学因为暴力判断素数导致超时，或者忽略了特殊情况而丢分。下面我们就从素数判断的优化开始，一步步构建完整的解决方案。

1.2 素数判断的优化策略

判断一个数是否为素数是最基础但也很关键的算法问题。我们先来看最直观的实现方式：

python复制def is_prime_naive(n):
    if n <= 1:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

这种实现时间复杂度是O(n)，当n很大时（比如题目中n可以达到10^8），这种写法肯定会超时。我们需要进行以下优化：

1. 缩小检查范围：只需要检查2到√n之间的整数即可，因为如果n有大于√n的因数，那么它必定有一个小于√n的对应因数。
2. 提前排除偶数：除了2以外，所有偶数都不是素数，可以提前判断。
3. 步长优化：检查奇数因子时，可以以2为步长跳过偶数。

优化后的实现：

python复制def is_prime(n):
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):