洛谷 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;?
}