洛谷 P1217 [USACO1.5] 回文质数 Prime Palindromes 刷题笔记

P1217 [USACO1.5] 回文质数 Prime Palindromes - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路 直接枚举 减枝优化判断

优化1 只有偶数才会是质数 

优化2 回文数的判断次数要优于检查素数 

先判断是否为回文数再检查是否为质数

if( hw(i)&&isprime(i))

这里有关于&&的条件 一但左边函数 为 0 右边函数 不再进行判断 

#include<iostream>
using namespace std;

int isprime(int x){
    for(int i=3;i*i<=x;i+=2){
        if(x%i==0){
            return 0;
        }
    }
    return 1;
    
}
int hw(int x)
{
    int res=0;
    int before=x;
    int t;
    while(x){
        
        t=x%10;
        res=res*10+t;
        x/=10;
    }
     
    if(res==before){
        return 1;
    }else{
        return 0;
    }
}
int main(){
    int a,b;
    cin>>a>>b;
    if(a%2==0){
        a++;
    }

    for(int i=a;i<=b;i+=2){
        
        if( hw(i)&&isprime(i)){
            printf("%d\n",i);
        }
    }
    
    return 0; 
}