66 TLE求调，闭关！！！

dream_dad @ 2024-10-06 11:31:47

#include<bits/stdc++.h>
using namespace std;
int a[100000000],prime[100000000],cnt=0;
string s;
void to_str(int n)
{
    s="";
    while(n!=0)
    {
        s+=n%10+'0';
        n/=10;
    }
}
bool pss(int num)
{
    if(num==1)
        return 0;
     if(num==2||num==3)
        return 1;
     if(num%6!=1&&num%6!=5)
        return 0;
     int tmp=sqrt(num);
     for(int i=5;i<=tmp;i+=6)
        if(num%i==0||num%(i+2)==0)
           return 0;
     return 1;
}
bool phw(string s)
{
    string s1=s;
    reverse(s1.begin(),s1.end());
    if(s==s1)return true;
    else return false;
}
int main()
{
    int n,m;
    cin>>n>>m;
    pss(m);
    int x;
    for(int i=n;i<=m;i++)
    {
        x=i;    
        to_str(x);
        if(i==9989800)
            return 0;
        if(pss(i)&&phw(s))
            cout<<i<<endl;
    }
    return 0;
}

by fifast @ 2024-10-06 11:58:25

答案紧共参考！

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
bool su(int x)
{
    if(x<=1) return false;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0) return false;
    }
    return true;
}
int main()
{
    int cnt=0;
    for(int i=5;i<=9;i+=2) a[++cnt]=i;
    for(int i=1;i<=9;i+=2)
    {
        a[++cnt]=i*10+i;
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            a[++cnt]=i*100+j*10+i;
        }
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            a[++cnt]=i*1000+j*100+j*10+i;
        }
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                a[++cnt]=i*10000+j*1000+k*100+j*10+i;
            }
        }
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                a[++cnt]=i*100000+j*10000+k*1000+k*100+j*10+i;
            }
        }
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                for(int l=0;l<=9;l++)
                {
                    a[++cnt]=i*1000000+j*100000+k*10000+l*1000+k*100+j*10+i;
                }
            }
        }
    }
    for(int i=1;i<=9;i+=2)
    {
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                for(int l=0;l<=9;l++)
                {
                    a[++cnt]=i*10000000+j*1000000+k*100000+l*10000+l*1000+k*100+j*10+i;
                }
            }
        }
    }
  //上面是枚举所有的回文数
    int l,r;
    cin>>l>>r;
    for(int i=1;i<=cnt;i++)
    {
        if(su(a[i])==true&&a[i]>=l&&a[i]<=r) cout<<a[i]<<endl;//质数判断，不用a到b
    }
    return 0;
}

求关！

by laotingrui @ 2024-10-07 11:19:39

@dream_dad

提示:数位个数为偶数的回文数都是11的倍数，所以1000到9999和100000到999999的回文数都不是质数