【洛谷】P1217 [USACO1.5] 回文质数（AC详解）

#include <iostream>  //引入输入输出流头文件，用于实现标准输入输出操作，例如使用cin和cout
#include <cmath>    //引入数学函数库头文件，主要用于调用sqrt函数来求平方根，辅助判断质数
using namespace std;

//函数声明，用于判断一个整数是否为质数，接收一个整数参数，返回布尔值表示是否为质数
bool isPri(int x);  
//函数声明，用于判断一个整数是否为回文数，接收一个整数参数，返回布尔值表示是否为回文数
bool isPal(int x);  

int main()
{
    int a, b;
    //从标准输入读取两个整数，分别赋值给变量a和b，这两个整数将确定后续查找的区间范围
    cin >> a >> b;  

    //循环遍历从a到b（包含a和b）的每一个整数i
    for (int i = a; i <= b; i++)  
    {
        //通过按位与操作判断i是否为奇数，i & 1的结果为1则表示i是奇数，为0则表示是偶数
        //也可以直白点是if (i % 2 != 0)，时间差不多，是可以AC的
        if (i & 1)  
        {
            //调用isPal函数判断i是否为回文数，如果是回文数则进入下面的判断
            if (isPal(i))  
            {
                //调用isPri函数判断i是否为质数，如果是质数则输出该整数，每个整数占一行
                if (isPri(i))  
                    cout << i << "\n";  
            }
        }
    }
    return 0;
}

//定义函数isPri，用于判断传入的整数x是否为质数
bool isPri(int x)
{
    //如果x能被2整除（即x是偶数且不为2时），直接返回0，表示x不是质数
    if (x % 2 == 0)  
        return 0;

    int i;
    //从2开始到sqrt(x)遍历，尝试判断x能否被这些数整除，以此来确定x是否为质数
    for (i = 2; i <= sqrt(x); i++)  
    {
        //如果x能被i整除，说明x不是质数，直接返回0
        if (x % i == 0)  
            return 0;
    }
//如果循环结束后i大于sqrt(x)，意味着在2到sqrt(x)范围内没有能整除x的数，所以x是质数，返回1
    if (i > sqrt(x))  
        return 1;
}

//定义函数isPal，用于判断传入的整数x是否为回文数
bool isPal(int x)
{
    int ori = x;  //将传入的整数x保存到ori变量中，用于后续和反转后的数字进行对比
    int re = 0;    //用于存储x反转后的数字，初始化为0

    //当x大于0时，通过循环不断取出x的最低位数字添加到re中，实现数字的反转
    while (x > 0)  
    
    //取出x的最低位数字(通过取余操作),添加到re中,每次添加前先将re乘以10,实现数字位权的递增
        re = re * 10 + x % 10;  
        //将x缩小10倍（通过整除操作），去掉已经处理过的最低位数字
        x /= 10;  
    }
    //对比原数字ori和反转后的数字re,如果相等则返回1,表示x是回文数;否则返回0，表示不是回文数
    return ori == re;  
}

此题的最大难点在于范围过大，枚举时间复杂度高，容易TLE，那么优化代码提高效率就是重中之重（当然代码也要兼顾好写...）。这里我主要在三处地方优化代码提高了效率：

1. 在main函数中对奇数的筛选以及判断的技巧

• 具体代码体现及操作逻辑：
  在main函数中有如下代码片段：

for (int i = a; i <= b; i++)
{
    if (i & 1)
    {
        if (isPal(i))
        {
            if (isPri(i))
                cout << i << "\n";
        }
    }
}

这里使用了按位与操作符&，通过i & 1来判断i是否为奇数。按位与操作是将两个整数对应的二进制位进行逐位的与运算，数字1的二进制表示为00000001（以一个字节举例，实际在计算机中根据整型的字节数而定，但原理相同），当一个整数i与1进行按位与运算时，如果结果为1，就意味着i的最低位二进制位是1，根据二进制的特性，最低位为1的整数就是奇数，反之则为偶数。

• 效率提升方面的详细解释：
  在整个程序要从区间[a, b]中找出满足特定条件的数时，由于最终要求的数需要同时具备奇数、回文数以及质数这三个属性，提前把偶数排除掉能避免很多不必要的后续操作。从概率角度来看，在整数的分布中，奇数和偶数大致各占一半（不考虑特殊边界情况等）。如果不进行这个提前筛选，对于区间内的每一个数，无论奇偶，都要依次调用isPal函数去判断是否为回文数，再调用isPri函数去判断是否为质数。以一个较大的区间，比如[1, 10000]为例，总共要处理10000个数，如果不筛选奇数，那么就要执行10000次回文数判断和10000次质数判断相关的函数调用及内部操作；而通过i & 1筛选出奇数后，理论上只需要对大约5000个奇数进行后续的回文数和质数判断操作，大大减少了函数调用次数以及相应的计算量，从而显著提高了程序整体的运行效率，尤其在区间范围越大、数字越多时，这种效率提升效果就越明显。 

判断时采用 

 if (isPal(i))
        {
            if (isPri(i))
                cout << i << "\n";
        }

 而不采用

 if (isPal(i) && isPri(i))
     cout << i << "\n";

 原因是先判断是否为回文数再判断是否为质数也可以减少计算量哦~

2. 在isPri函数中对偶数的预处理及除数选取优化

• 对偶数的预处理：
  在isPri函数中，代码开头部分如下：

bool isPri(int x)
{
    if (x % 2 == 0)
        return 0;
    //后续代码省略（循环等相关代码）
}

这里通过x % 2 == 0来判断x是否为偶数。取余运算（%）是计算一个数除以另一个数后的余数，当x除以2余数为0时，就表明x能被2整除，也就是x是偶数。而根据质数的定义，除了2这个特殊的质数外，其他所有偶数都不可能是质数，因为质数是除了1和它自身外，不能被其他自然数整除的数，偶数都至少能被2整除（除了本身就是2的情况）。

例如，对于数字6，6 % 2 = 0，直接就能判断它不是质数，无需再进行后续复杂的判断操作；同样对于10、12等偶数，都可以通过这一步快速得出不是质数的结论，避免进入后面的循环去进一步尝试用其他数整除它来判断是否为质数，节省了大量不必要的计算资源和时间开销。特别是在处理大量数字的场景下，比如要判断1到100000之间所有数字是否为质数，其中偶数占了一半左右，如果没有这个提前判断偶数的步骤，循环部分的代码就要对这些偶数也逐个进行多余的判断操作，而有了这个判断后，就可以快速跳过这些偶数的相关流程，直接处理奇数情况，极大地提高了整体判断质数的效率。

• 除数选取优化（只使用奇数作为除数）：
  在isPri函数的循环部分，代码如下：

for (i = 3; i <= sqrt(x); i += 2)
{
    if (x % i == 0)
        return 0;
}

这里将循环的起始值设为3，步长设为2，使得循环中使用的除数i都是奇数。其背后的数学原理基于质数的因数特性。对于一个大于1的整数x，如果它不是质数，即它可以分解成两个因数相乘的形式（假设为a和b，且a <= b），根据数学推导，必然存在a <= sqrt(x)和b >= sqrt(x)这样的关系（可以通过简单的数学不等式推导得出，若x = a * b，两边同时开平方可得sqrt(x) = sqrt(a * b)，由于a <= b，所以a <= sqrt(x)）。

而且除了2以外，其他偶数都可以表示为2乘以另一个整数，所以在判断一个数是否能被除自身和1以外的数整除时，只需要考虑奇数作为可能的因数即可。例如，对于数字25，其因数有1、5、25，在判断它是否为质数时，我们只需要用奇数去尝试整除它就行，从3开始（因为已经提前处理了偶数情况且1和它本身不需要判断），步长为2，也就是尝试用3、5（刚好能整除，此时就可以判断它不是质数了）等奇数去判断，而不需要用4、6、8等偶数去尝试整除它，因为这些偶数不可能是它除了自身和1以外的因数。

从效率角度来看，在判断一个较大的数是否为质数时，比如123457，常规的做法如果是从2开始逐个遍历到sqrt(123457)，会有大量的偶数作为除数参与判断，而这些偶数除了2本身外是不可能成为其因数的，属于无效的判断操作。通过只使用奇数作为除数，大致能减少一半的循环次数，显著降低了计算量，让判断质数这个操作在面对较大数字或者大量数字判断时，执行速度更快，从而提升了整个程序的运行效率。

感觉有帮助的小伙伴不妨点点赞和收藏~