思路与算法

依次枚举区间[M,N]中的每个数。试除到平方根判断原数是否为素数，再通过不断取个位并乘10累加得到十进制反序数，判断它是否也是素数。两个条件都满足时输出原数，数与数之间插入逗号；如果完全没有合格数，输出No。

正确性说明

试除法对小于2的数返回假。若n为合数，一对因子中必有一个不超过sqrt(n)，因此检查到平方根不会漏掉合数；素数则不含这些因子，所以判定准确。反序循环每次取出当前最低位并接到结果尾部，最终恰为十进制反序。于是输出条件与真素数定义等价。区间按从小到大完整枚举，故结果无遗漏、无重复且有序；没有结果时No正确。

复杂度

令U=N，区间长度K=N-M+1。每个数最多做两次O(sqrt(U))试除以及O(log U)位数反序，在本题U<=100000范围内反序也不超过100000，总时间O(K*(sqrt(U)+log U))，额外空间O(1)，初始化O(1)。不保存所有输出，边枚举边输出。

易错点

闭区间包含两个端点；1不是素数。回文素数也可以入选，不要求反序后不同。反序会自然去掉前导零。输出英文逗号，首尾无逗号；无结果是首字母大写No，不是empty或NO。

参考代码（C++11）

#include <iostream>
using namespace std;
bool prime(int n) {
    if (n < 2)
        return false;
    for (int d = 2; d * d <= n; ++d)
        if (n % d == 0)
            return false;
    return true;
}
int reversed(int n) {
    int r = 0;
    while (n) {
        r = r * 10 + n % 10;
        n /= 10;
    }
    return r;
}
int main() {
    int m, n;
    cin >> m >> n;
    bool found = false;
    for (int x = m; x <= n; ++x)
        if (prime(x) && prime(reversed(x))) {
            if (found)
                cout << ',';
            cout << x;
            found = true;
        }
    if (!found)
        cout << "No";
    cout << '\n';
}