c++TLE了最后三个点，请问怎么优化

yinbe @ 2023-01-08 13:45:54

#include<iostream>
using namespace std;
bool isPrime(int n)
{
    if(n<2)
    {
        return false;
    }
    if(n==2)
    {
        return true;
    }
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
bool huiwen(int n)
{
    int m=0,a=n;
    while(a)
    {
        m=m+a%10;
        a/=10;
        m*=10;      
    }
    m/=10;
    if(m==n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    for(int i=a;i<=b;i++)
    {
        if(isPrime(i)&&huiwen(i))
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

by VitrelosTia @ 2023-01-08 13:47:39

@LuYe0219 暴力枚举必然超时，我们可以考虑回文质数的性质，比如位数必然是奇数。

by Eric_Shi @ 2023-01-08 14:06:03

改成这样试试

if(a%2 == 0)
    a += 1;
for(int i=a;i<=b;i+=2)
    {
        if(isPrime(i)&&huiwen(i))
        {
            printf("%d\n",i);
        }
    }

by yinbe @ 2023-01-08 14:10:03

都改成这样了还是一样TLE最后三个点

#include<iostream>
using namespace std;
bool isPrime(int n)
{
    if(n<2)
    {
        return false;
    }
    if(n==2)
    {
        return true;
    }
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
bool huiwen(int n)
{
    int m=0,a=n;
    while(a)
    {
        m=m+a%10;
        a/=10;
        m*=10;      
    }
    m/=10;
    if(m==n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool weishu(int n)
{
    if(n==11)
    {
        return true;
    }
    int cnt=0;
    while(n)
    {
        n/=10;
        cnt++;
    }
    if(cnt%2==0)
    {
        return false;
    }
    else
    {
        return true;
    }
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a%2==0)
    {
        a-=1;
    }
    for(int i=a;i<=b;i+=2)
    {
        if(isPrime(i)&&huiwen(i)&&weishu(i))
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

by Eric_Shi @ 2023-01-08 18:54:46

再加上这个呢？

if (b>=10000000) b=9999999;
//除了11以外，一个数的位数是偶数的话，不可能为回文数素数

by mzc0forever @ 2023-01-09 16:06:10

1.不能是偶数且不超过9999999 2.是回文 3.是素数

by yinbe @ 2023-01-11 11:22:52

我现在才发现换一下判断顺序就好了

#include<iostream>
using namespace std;
bool isPrime(int n)
{
    if(n<2)
    {
        return false;
    }
    if(n==2)
    {
        return true;
    }
    for(int i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            return false;
        }
    }
    return true;
}
bool huiwen(int n)
{
    int m=0,a=n;
    while(a)
    {
        m=m+a%10;
        a/=10;
        m*=10;      
    }
    m/=10;
    if(m==n)
    {
        return true;
    }
    else
    {
        return false;
    }
}
bool weishu(int n)
{
    if(n==11)
    {
        return true;
    }
    int cnt=0;
    while(n)
    {
        n/=10;
        cnt++;
    }
    if(cnt%2==0)
    {
        return false;
    }
    else
    {
        return true;
    }
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    if(a%2==0)
    {
        a-=1;
    }
    for(int i=a;i<=b;i+=2)
    {
        if(weishu(i)&&huiwen(i)&&isPrime(i))
        {
            printf("%d\n",i);
        }
    }
    return 0;
}

这样就过了

by chenhongyicc @ 2023-01-14 18:04:02

@LuYe0219 我感觉时间复杂度还可以在少一点

就是把定义质数函数的

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

改成

for(int i = 2 ;i<=sqrt(n); i++)//或是log2

虽然我这道题也是tle，但是这个地方没问题，这样可以减少时间复杂度

by yinbe @ 2023-01-14 19:25:36

sqrt和i * i的时间复杂度那个少啊