无法输出,看不出来哪儿出了问题,求助求助!

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

77Glorious @ 2023-09-20 16:54:14

#include<iostream>
using namespace std;

bool isp(int x){

    for(int i=3;i*i<=x;i+=2){
        if(x%i==0) return false;
    }
    return true;
}

/*
例: 
12321 -> 12321
*/ 

bool hw(int x){
    int sum=0,tmp=x;
    while(tmp!=0){
        sum*=10;//进位
        sum+=tmp%10;
        tmp/=10; 
    }//反转位数 
    if(sum==tmp) return true;
    return false;
}

int main(){
    int a,b;
    cin>>a>>b;
    if(a%2==0) a++;//变奇数 
    if(b>10000000) b=10000000;  //除去1e7以上的数 
    for(int i=a;i<=b;i+=2){//全部枚举奇数 

        if(isp(i)&&hw(i)) cout<<i<<endl;

    }

    return 0;
}

by InversionShadow @ 2023-09-20 16:56:59

hw 哪里,最后应该是 sum==x,因为 tmp 改变了


by 77Glorious @ 2023-09-20 17:04:55

@ydq1101 感谢感谢!但是为啥优化了非奇数和大于1e7的数还是有俩tle呢()


by InversionShadow @ 2023-09-20 17:16:41

@Vanxia1266 把 if 的两个函数调换顺序试一下


by 77Glorious @ 2023-09-20 17:19:23

@ydq1101 过了过了!所以说为啥不能先判断质数再判断回文呢


by InversionShadow @ 2023-09-20 18:46:29

@Vanxia1266 因为 c++ 采用了这种模式:如果是 a&&b,且 a=0,那么不管 b 的取值,a&&b 总是为 0,所以 c++ 会跳过,所以把原来的非回文质数判断的时间复杂度从 O(\sqrt{n}) 降到了常数级。

说句闲话,本来要回你的,然后 luogu 炸了,就上不了了,,,


|