求助,三个超时怎么优化

lijiayi11 @ 2023-08-22 22:31:25

#include<bits/stdc++.h>

using namespace std;

bool prime(int a)
{

    if(a<2)
        return 0;
    for(int i=2;i<=sqrt(a);i++)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}

bool whe(int a)
{

    int t=a,x=1;
    string m;
    while(t!=0)
    {
        m.push_back(t%10+'0');
        t/=10;
        x*=10;
    }
    for(int i=0;i<m.size()/2;i++)
    {
        if(m[i]!=m[m.size()-1-i])
        {
            return 0;
        }
    }
    return 1;
}

int main()
{

    int n,m;
    cin>>n>>m;
    for(int i=n;i<=m;i++)
    {
        if(prime(i)==1)
        {
            if(whe(i)==1)
                cout<<i<<endl;
        }
        //cout<<i<<":"<<prime(i)<<" "<<whe(i)<<endl;
    }
    return 0;
}

by To_our_starry_sea @ 2023-08-22 22:35:59

先枚举回文数，再判断素数 @lijiayi11

by heyx0201 @ 2023-08-22 22:45:16

@lijiayi11 这题硬是要写质数筛的话只能写欧拉筛

by heyx0201 @ 2023-08-22 22:47:21

@To_our_starry_sea 顺便问一问，这题欧拉筛严格意义上能过吗

by lijiayi11 @ 2023-08-22 23:00:24

@To_our_starry_sea 确实调整完,就剩一个超时了

by talkwithcpp @ 2023-08-22 23:39:39

1.你的质数判断可以加个优化：

if(a%2!=0) return 0;

for循环同时改为

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

其中i * i是个人习惯,你的也行

2.回文判断不用这么写，看我的：

bool f2(int n)
{
    int s=0,w=n;
    while(n!=0)
    {
        s=s*10+n%10;
        n/=10;
    }
    if(w==s) return true;
    else return false;
}

自己手动模拟几遍就会了。我的这个方法对于数是很快的，s * 10可以利用2进制优化为 （s<<3）+(s<<1),不懂的话不用管，以后学快读会见到。如果对于一个字符串或高精度数的话最好一前一后的两个下标指针判断。似乎有道题会用到

3.主函数判断中要先判回文再判质数，因为回文数少于质数并且判断比质数快

4.枚举数时候，循环中i++要改为i+=2,这个优化可以跳过一半的数，这个优化用了之后要注意循环开始必须是奇数，所以前面要特判下。 这个优化用了后优化1就不用了，因为已经跳过了可以被2整除的质数。

5.还有个优化是位数为偶数的数没有回文数。

6.最后一个点有个优化，就是只枚举到9989899，这是1亿内最大的回文质数。

这道题我当时做的时候改了好几天，可以从这道题学到不少技巧，值得细细研究。

by To_our_starry_sea @ 2023-08-23 15:04:25

@Codehyx欧拉筛应该不行吧，毕竟是 O(n) 的。