88分

renzhanwen @ 2024-06-11 18:10:58

#include<bits/stdc++.h>
using namespace std;
long long a,b;
int main() 
{
    cin>>a>>b;
    bool isprime[b+100],vis[b+100];
    vector<int> primes;
    for(int i=1;i<=b+100;i++)
        isprime[i]=true;
    for(int i=1;i<=b+100;i++)
        vis[i]=false;
    for(int i=2;i<=b;i++) 
    {
        if(isprime[i])
            primes.push_back(i);
        for(int j=0; j<primes.size(); j++) 
        {
            int p=primes[j];
            if(i*p>b) break;
            isprime[i*p]=false;
            if(i%p==0) break;
        }
    }
    for(int i=0;i<primes.size();i++)
        vis[primes[i]]=true;
    for(int i=a;i<=b;i++)
    {
        if(vis[i]==false) continue;
        int m=i,aa[100],kk=0;
        bool s=true;
        while(m)
        {
            kk++;
            aa[kk]=m%10;
            m/=10;
        }
        for(int j=1;j<=kk/2;j++)
            if(aa[j]!=aa[kk-j+1])
            {
                s=false;
                break;
            }
        if(s==false)
            continue;
        cout<<i<<endl;
    }
    return 0;
}

by kevinZ99 @ 2024-06-11 18:23:52

@syex_renzhanwen

MLE 的主要原因就是 bool 数组开的太大了，可以使用bitset来进行压缩，bitset的空间复杂度是 \mathcal{O}\left(\frac{n}{w}\right)

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
bitset<N> isprime,vis;
long long a,b;
int main() 
{
    cin>>a>>b;
    vector<int> primes;
    for(int i=1;i<=b+100;i++)
        isprime[i]=true;
    for(int i=1;i<=b+100;i++)
        vis[i]=false;
    for(int i=2;i<=b;i++) 
    {
        if(isprime[i])
            primes.push_back(i);
        for(int j=0; j<primes.size(); j++) 
        {
            int p=primes[j];
            if(i*p>b) break;
            isprime[i*p]=false;
            if(i%p==0) break;
        }
    }
    for(int i=0;i<primes.size();i++)
        vis[primes[i]]=true;
    for(int i=a;i<=b;i++)
    {
        if(vis[i]==false) continue;
        int m=i,aa[100],kk=0;
        bool s=true;
        while(m)
        {
            kk++;
            aa[kk]=m%10;
            m/=10;
        }
        for(int j=1;j<=kk/2;j++)
            if(aa[j]!=aa[kk-j+1])
            {
                s=false;
                break;
            }
        if(s==false)
            continue;
        cout<<i<<endl;
    }
    return 0;
}

by renzhanwen @ 2024-06-11 18:25:58

@kevinZ99 已AC 谢谢