题目

小f绕过了对离岛的封锁，来到了稻妻的白狐之野，遇到了带着狐狸面具的花散里。花散里出于某些原因不能够进行一个古老的仪式——神樱大祓，所以她请求小f帮忙，热心的小f答应了下来。在前往神樱大祓的一个地点时，小f遇到了一个镇守者。镇守者要考验小f的智慧，只有拥有大智慧的人才能进入其中，完成仪式。他的问题是这样的：找出区间 [l, r] 内的真素数。

真素数的定义为：如果一个数 p 为素数，而且其反序也为素数，则 p 为真素数。

输入：两个数 l, r 表示闭区间的范围。
输出：输出 [l, r] 内的真素数，每个真素数用空格隔开。如果区间内不存在真素数，请输出 No!。
数据范围：1 ≤ l, r ≤ 10000。

样例：

输入

10 35

输出

11 13 17 31

思路

写两个函数：isPrime 枚举到 √x 判断素数；reverse 用 %10 取末位、*10 腾位、/10 移位三步循环求反序数。枚举区间内每个数，两者均为素数即为真素数输出；用 notFound 标记无解，最后决定是否输出 No!。

C++ · p75.cpp 
#include<bits/stdc++.h>
using namespace std;

bool isPrime(int x){
    bool prime_flag=true;
    for(int c=3;c*c<=x;c+=2){
        if(x%c==0){
            prime_flag=false;
        }
    }
    if(x<2){
        return false;
    }else if(x==2){
        return true;
    }else if(x%2==0){
        return false;
    }else if(!prime_flag){
        return false;
    }else{
        return true;
    }
}

int reverse(int x){
    int rev=0;
    while(x!=0){
        rev=rev*10+x%10;
        x/=10;
    }
    return rev;
}

int main(){
    int l,r;
    cin>>l>>r;
    bool notFound=true;
    for(int c=l;c<=r;c++){
        int re=reverse(c);
        if(isPrime(c)&&isPrime(re)){
            cout<<c<<" ";
            notFound=false;
        }
    }
    if(notFound) cout<<"No!"<<endl;
    return 0;
}

复杂度分析

  • 时间复杂度：O((r−l+1) · √r)，每个数调用一次 isPrime，枚举到 √x。
  • 空间复杂度：O(1)。
今日感受

写反序函数时，最容易犯的错是先加再乘——结果多乘了一次。后来弄明白：要先 rev *= 10 腾出位置，再 rev += x % 10 填入新数字，顺序不能反。另外 notFound 的判断条件也写反了一次，找 bug 时才意识到变量名要和逻辑方向对齐，不然很容易绕糊涂。

← 返回菜鸟的coding