最后三个TLE,求解

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

code_AZ @ 2024-10-14 19:48:57

#include <iostream>
#include<cmath>
using namespace std;
bool isprime(int i)
{
    bool judge=true;
    for(int j=2;j<=sqrt(i);j++)
    {
        if(i%j==0) return false;
    }
    return true;
}
int main()
{
    int n,m,judge_arr[1000];
    cin>>n>>m;
    for(int i=n;i<=m;i++)
    {
        int temp=i;
        int count=1;
        if(isprime(i)) 
        {
            while(i!=0)
            {
                judge_arr[count]=i%10;
                i=i/10;
                count++;
            }
            count--;
            int plus=count+1;
            bool judge_f=true;
            for(int k=count;k>=(plus/2);k--)
            { 
                if(judge_arr[k]!=judge_arr[plus-k]) 
                    {
                        judge_f=false;
                        break;
                    }
            }
            i=temp;
            if(judge_f) cout<<temp<<endl;
        }
    }
    return 0;
}

by 18092188287zz @ 2024-10-15 20:04:56

因为回文质数必为11的倍数(2除外,自己试)

所以就可以改进算法,在列举出每个奇数后判断是否是回文质数就行了。


by 18092188287zz @ 2024-10-15 20:20:14

@code_AZ


by code_AZ @ 2024-10-16 12:52:13

@18092188287zz 好的,我去试试


|