求不超时方法，玄关

KevinTYX @ 2024-10-07 19:19:32

#include <bits/stdc++.h>
using namespace std;
bool x(int a)
{
    for(int i=2;i<a;i++)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}
bool y(int a)
{
    int f=a;
    int sum=0;
    while(a)
    {
        sum*=10;
        sum+=a%10;
        a/=10;
    }
    if(sum==f)
    {
        return 1;
    }
    return 0;

} 

int main()
{
    int a,b;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(x(i))
        {
            if(y(i))
            {
                cout<<i<<endl;
            }
        }

    }
    return 0;
}

by wanglvyan @ 2024-10-07 19:23:18

i<a改i*i<=a

by wanglvyan @ 2024-10-07 19:25:07

在x函数中

by wanglvyan @ 2024-10-07 19:29:07

@ KevinTYX

by Wyl17370863080 @ 2024-10-07 19:34:58

打表

by OIer_bcx_ @ 2024-10-07 19:36:23

1.

for(int i=2;i<a;i++)

改为

for(int i=2;i*i<=a;i++)

2.

if(x(i))
{
    if(y(i))
    {
        cout<<i<<endl;
    }
}

改为

if(y(i))
{
    if(x(i))
    {
        cout<<i<<endl;
    }
}

3.

while(a)
{
    sum*=10;
    sum+=a%10;
    a/=10;
}

改为

while(a&&sum<=f)
{
    sum*=10;
    sum+=a%10;
    a/=10;
}

by OIer_bcx_ @ 2024-10-07 19:36:45

@KevinTYX

by chx_happy @ 2024-10-07 19:37:14

@KevinTYX 可以预处理筛出10^4以内的质数，在判断质数的函数中用质数数组[2,sqrt(x)]中的数试除

by chx_happy @ 2024-10-07 19:39:20

@OIerbcx 两处都改仍然超时，建议质数筛

by OIer_bcx_ @ 2024-10-07 19:44:24

@chx_happy ??? 有3处

by chx_happy @ 2024-10-07 19:45:26

@OIerbcx 对不起QAQ