提交了5次，前四次TLE，优化后 #3 WA了，求错因

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

ChenMoyan6 @ 2023-07-19 15:11:13

用的暴力枚举，优化了几个地方：

从偶数开始，每次+2，排除奇数
先判断回文，再判断质数
跳过偶数位的数（除了2位数）

运行到9989899（后面没了）

#include<bits/stdc++.h>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
if(a%2==0) a++;//优化1.
b=min(9989899,b);//优化4.
for(int i=a;i<=b;i+=2)//优化1.
{
int k=i,t=0,ws=0;
while(k)
{
    t=t*10+k%10;
    k/=10;
    ws++;
}
if(ws%2==0&&ws!=2)
    i=i*10+1;//优化3.
if(t==i)//优化2.
{
    bool zs=1;
    for(int j=3;j*j<=i;j+=2)
        if(i%j==0) zs=0;
    if(zs==1)
        cout<<i<<"\n";
}
}
return 0;
}

c++谢谢

~~解释得这么清楚，看得懂吧~~

by _空白_ @ 2023-07-19 15:25:23

@ChenMoyan6 偶数位也有符合的数，所以你优化三是错的，删了就对了

by _空白_ @ 2023-07-19 15:30:50

@ChenMoyan6 当然有可能我说的不对，但你的优化3确实写错了

by ChenMoyan6 @ 2023-07-19 17:18:56

@_空白_ 过了，谢谢…\(^_^)/

by Coffee_Moew @ 2023-08-01 14:38:33

@空白优化三是对的，除了11，其他一定是11的倍数

by Coffee_Moew @ 2023-08-01 14:39:05

@ChenMoyan6

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,ts,fz,zs,ws;
    cin>>a>>b;
    if(a%2==0) a++;
    if(b>9989899) b=9989899;
    for(int i=a;i<=b;i=i+2)
    {
        ts=i;
        fz=0;
        zs=1;
        ws=0;
        while(ts)
        {
            fz=fz*10+ts%10;
            ts=ts/10;
            ws++;
        }
        if(ws==2&&i!=11) continue;
        if(fz==i)
        {
            for(int j=2;j*j<=i;j++)
            if(i%j==0)
            {
                zs=0;
                break;
            }
            if(zs) cout<<i<<endl;
        }
        else continue;
    }
    return 0;
}