C++33分TLE蒟蒻求助,大佬帮帮吧

P1217 [USACO1.5] 回文质数 Prime Palindromes

SilVeR__WolF @ 2023-11-26 15:23:17

#include<bits/stdc++.h>
using namespace std;
int main(void){
    int a,b,num,sum,k;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        num=i;//将i的值拷贝到num里,因为一会儿要对num的值做改动 
        sum=0;//sum用来存储num倒序的值 
        while(num)
        {
            sum=sum*10+num%10;
            num/=10;
        }//while循坏是在将num倒序后保存到sum里面 
        if(sum==i)//如果num(i的备份)倒序后还等于原先的i,则说明i是回文数,下面判断i是否为质数 
        {
            k=0;
            for(int j=2;j<i;j++)
            {
                if(i%j==0)
                k=1;
            }
            if(k==0)//如果在2到i-1里没有一个是i的因数,则i为质数,输出i 
            {
                cout<<i<<endl;
            }
        }
    }
}

明明本地唰一下就出了,可到这儿就TLE了,求调,万分感谢!


by 123WRz @ 2023-12-02 11:13:04

偶数位的回文数不是质数,能除11,所以先判断位数就不TLE了,记得开O2


by Azzero @ 2023-12-02 11:41:17

你这个很容易超时的,你可以试试5~99999999,后面数字多了之后,判断质数哪里超慢的。

    for(int j=2;j<i;j++)
    {
        if(i%j==0)
            k=1;
    }

一个是判断质数的时候,只需要判断到I的算术平方根就行了,没必要到i-1,另外我把你的代码改了,交上去还是有一组数据超时,我把cin、Cout都改成scanf printf还是一样。 感觉另外一个超时原因可能是CPP的头文件速度可能比较慢啊。


by SilVeR__WolF @ 2023-12-09 13:42:39

@Azzero @123WRz 感谢两位大佬,AC了


by Azzero @ 2023-12-09 14:13:12

@SilVeR__WolF OOK


|