题解：P1217 [USACO1.5] 回文质数 Prime Palindromes

Luogu_Wangzhi · 2025-06-29 11:52:42 · 题解

题解：[USACO1.5] 回文质数 Prime Palindromes。

题意：

输出从 a 到 b 的所有不仅是质数，还是回文数的数字。

解法：

暴力枚举。

减小时长方法：

• 所有数中除了 2，其他偶数都不是质数，数据范围没有 2，所以特判掉。

• 在 5 到 10^8 范围内回文数比质数少，所以先判断是否是回文数，再判断是否是质数。

code

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    long long a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++){
        if(i%2==0){//特判偶数
            continue;
        }
        int w=i,s=0;
        while(w!=0){//判断是否为回文数
            s=s*10+w%10;
            w/=10;
        }
        if(s!=i){
            continue;
        }
        int f=0;//判断是否为质数
        for(int j=2;j*j<=i;j++){
            if(i%j==0){
                f=1;
                break;
            }
        }
        if(f==0){
            cout<<i<<endl;
        }
    }

}