最后的点TLE88分求助

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

123WRz @ 2023-10-06 14:18:21

#include <bits/stdc++.h>
using namespace std;
bool is_prime(int n){
    if(n==1||n==0) return false;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}

bool hws(int k){
    int a[10],i=0;     
    while (k>0){a[i]=k%10;k/=10;i++;}
    for(int j=0;j<i;j++)if(a[j]!=a[i-j-1])return false;   
    return true;     
}
bool ws(int n){
    if(n>=10 && n<100 && n!=11 || n>=1000 && n<10000)return false;
    if(n>=100000 && n<1000000 || n>=10000000 && n<100000000)return false;
    return true;
}
int main(){
    int a,b;
    scanf("%d%d",&a,&b);
    if(a==2) printf("2\n");
    if(a%2==0) a++;
    for(int i=a;i<=b;i+=2){
        if(!hws(i)) continue;
        if(!ws(i)) continue;
        if(!is_prime(i)) continue;
        printf("%d\n",i);
    }
}

by kevinchen126 @ 2023-10-06 15:47:03

1:lz可以考虑枚举奇数位的数,再特判11 如:i=1~9.

if(a<=11&&11<=b)

i=101~999

i=10001~99999

i=1000001~9999999

i=100000001~999999999

其中下限可以用max(a,?),上限用min(b,?)

2:质数判断部分也可以先特判2,再从3来+=2


by kevinchen126 @ 2023-10-06 15:48:13

@123WRz


by 123WRz @ 2023-10-06 16:34:24

thank


by Caitianmo @ 2023-10-06 17:00:39

开o2就可以过了


|