感觉对的怎么超时了求解

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

aichiyuJOJO @ 2024-10-23 16:25:31

#include<stdio.h>
int su(int x)
{
for(int i=2;i<x;i++)
{
if(x%i==0)
return 0;
}
return 1;
}
int hui(int x)
{
int s,y=0;
s=x;
while(s>0)
{
y=y*10+s%10;
s=s/10;
}
if(y==x)
return 1;
else
return 0;
}
int main()
{
int m,n;
scanf("%d%d",&n,&m);
for(int i=n;i<=m;i++)
{
if(su(i)&&hui(i))
{
printf("%d\n",i);
}
}
return 0;
}

by XYC_1212 @ 2024-10-23 16:48:47

素数函数改成i*i<=x,x的因子最多到x的开平方

把回文判定放在前面判断,最多九次,会比之前快一点。

加特判,m>=9989899(一亿里最大的回文素数,打表得出)时m=9989899,不然从n~m加上函数时间会超时


|