回文质数 Prime Palindromes

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

生成回文数并判质数，输出 [a,b] 内的回文质数

洛谷
例题

正文

// 原题：https://oj.yecheng.tv/p/1383
// 题意：找出区间 [a,b]（b<=1e8）内所有既是质数又是回文数的数，每行一个。
// 思路：按位数构造回文数（从半边镜像），再判质数，筛选落在 [a,b] 的。
// 复杂度：回文数约 2e4 个，逐个试除判素。
// 易错点：直接枚举 [a,b] 太慢，必须先生成回文数；注意 11 这类偶位回文。
#include <iostream>
#include <cmath>
using namespace std;
bool isP(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; i++) if(x % i == 0) return false;
    return true;
}
int main(){
    int a, b;
    cin >> a >> b;
    for(int len = 1; len <= 8; len++){
        int half = (len + 1) / 2;
        int st = 1, en = 1;
        for(int i = 0; i < half - 1; i++){ st *= 10; en *= 10; }
        en *= 10;
        for(int h = st; h < en; h++){
            int p = h;
            int t = (len % 2 == 0) ? h : h / 10;
            while(t){ p = p * 10 + t % 10; t /= 10; }
            if(p >= a && p <= b && isP(p)) cout << p << endl;
        }
    }
    return 0;
}

回文质数 Prime Palindromes

正文

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