回文质数

洛谷·深入浅出 · 代码 · cpp · 难度 4/5 · 共 1170 字

生成 [a,b] 内所有回文质数

洛谷
练习

正文

// 原题：https://oj.yecheng.tv/p/1440
// 题意：输出 [a,b] 内所有“既是质数又是回文数”的数，一行一个。
// 思路：按位数生成回文数（前半段镜像），再判质数并落在 [a,b]；收集后排序输出。
// 复杂度：约 O(回文数个数 * sqrt) 可过 1e8。
// 易错点：先生成回文再判质比逐个判快得多；偶数位回文整体镜像，奇数位镜像时去掉中心位。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isprime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
    return true;
}
long long ipow(int b, int e){
    long long r = 1;
    while(e--) r *= b;
    return r;
}
int main(){
    int a, b;
    cin >> a >> b;
    vector<int> res;
    for(int len = 1; len <= 8; len++){
        int h = (len + 1) / 2;
        long long start = ipow(10, h - 1), end = ipow(10, h) - 1;
        for(long long half = start; half <= end; half++){
            string s = to_string(half);
            string t = s;
            if(len % 2 == 0) reverse(t.begin(), t.end());
            else { t.pop_back(); reverse(t.begin(), t.end()); }
            int v = stoi(s + t);
            if(v >= a && v <= b && isprime(v)) res.push_back(v);
        }
    }
    sort(res.begin(), res.end());
    for(int x : res) cout << x << endl;
    return 0;
}

回文质数

正文

洛谷·深入浅出的其它内容