为啥这份代码不开O2 TLE,开了之后AC

rnf5114 @ 2024-01-06 13:46:18

# include<iostream>
# include <cstring>
#include<math.h>
using namespace std;

int zs(int n){
    for(int i=2;i*i<=n;i++){
        if(n%i==0) return 0;
    }
    return 1;
}

int hw(int num){
    int t=num,ans=0;
    while(t){
        ans = ans*10 + t%10;
        t/=10;
    }

    if(num==ans) return 1;
    else return 0;
}

int main()
{   
    int a,b;
    cin >> a >> b;
    for(int i=a;i<=b;i++){
        if(i%2==0)
            continue;
        if(hw(i)){
            if(zs(i)){
                cout << i << "\n";
            }
        }
    }

    return 0;
 } 

by Humour_Fz @ 2024-01-06 13:50:04

@rnfmabj5114 建议把判断质数改成提前筛好质数

by rnf5114 @ 2024-01-06 13:51:15

@XZH114514 我是指说O2是做了些啥优化导致这份代码跑的飞快

by Humour_Fz @ 2024-01-06 13:51:55

@rnfmabj5114 想这样

#include<bits/stdc++.h>
using namespace std;
int l,r,len;
bool zsb[9989900];
bool hws(int x){
    string s=to_string(x);
    int len=s.size();
    for(int i=0;i<len/2;i++) if(s[i]!=s[len-i-1]) return 0;
    return 1;
}int main(){
    ios::sync_with_stdio(0);
    cin.tie(),cout.tie();
    cin>>l>>r,l=l/2*2+1,r=min(r,9989899);
    for(int i=1;i<=r;i++)zsb[i]=1;
    for(int i=2;i*i<=r;i++)if(zsb[i])for(int j=i;j<=r/i;j++)zsb[i*j]=0;
    for(int i=l;i<=r;i+=2)if(zsb[i]&&hws(i))cout<<i<<"\n";
    return 0;
}

by Humour_Fz @ 2024-01-06 13:54:52

@rnfmabj5114 加上 b=min(b,9989899); O2不开也可以

by yujieai @ 2024-01-08 15:34:52

感谢感谢题解,之前就是回你这个方法但忘了，终于又找到了，赶紧保存