求帮改,第九个tle

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

_Warfarin_ @ 2023-09-24 16:43:35

#include<iostream>

bool a[100000000]; 

void k(int e)
{
    for(int i=2;i*i<=e;i++) 
    { 
        if(a[i]==0)  
            for(int j=i*i;j<=e;j+=i) 
                a[j]=1;  
    }
}

using namespace std;

int main ()
{
    int b,e;

    cin>>b>>e;
    a[1]=1;  
    k(e);
    for(int i=1;i<=e;i++)
    {
        if(a[i]==1)
            continue;
        int b=i,s=i;
        int sum=0;
        while(s>0)
        {
            int t=s%10;
            sum*=10;
            sum+=t;
            s/=10;
        }
        if(b!=sum)
            a[i]=1;
    }
    for(int i=b;i<=e;i++)
        if(a[i]==0)
            cout<<i<<endl;

    return 0;  
}

by _zhang @ 2023-09-24 17:03:54

有更优的算法


by _zhang @ 2023-09-24 17:06:54

枚举前一半位,之后的一半数位根据回文数的定义可以确定(《深入浅出基础篇》不是有吗


by _zhang @ 2023-09-24 17:09:24

@fengce


by _Warfarin_ @ 2023-09-24 17:30:00


|