王码编程 OJ 首页 问题列表 比赛 社团 排行榜 记录 新闻通知 课程 帮助 暂无头像 De. 首页 问题 回文质数 不会有人先筛质数吧 虚空终端 • 2年前

每日刷题掉坑（114514/1） 在大部分人的潜意识里，质数远比回文数好筛，但真的是这样吗？ 质数在剩余个数方面不赖，但是时间复杂度O(n)、O(sqrt(n))这样的大数字却经常被忽略 去掉2和5的倍数，剩下的回文数又有多少呢？ 正是这个原因，使得这题的TLE率特别高（不排除我前面试了n多次） 外加一个查博客偶然所得的规律（见最后），代码就大功告成了

include

include

int huiwen(int k) {

int a[10],i=0,j;
while (k>0)
{
    a[i]=k%10;
    k/=10;
    i++;
}
for (j=0; j<i; j++)
    if (a[j]!=a[i-j-1])
        return 0;
return 1;

}

int hwlength(int k) {

int a[10],i=0;
while (k>0)
{
    a[i]=k%10;
    k/=10;
    i++;
}
return (i);

}

int prime(int k) {

int i;
for (i=3; i*i<=k; i+=2)
    if (k%i==0)
        return 0;
return 1;

}

int extend(int k) {

int i,s=1;
for (i=0; i<k; i++)
    s*=10;
return (s);

}

int main() {

int a,b,i,j;
scanf("%d%d",&a,&b);
for (i=a; i<=b; i++)
{
    if (i%2==0&&i!=2)
        continue;
    if (i%5==0&&i!=5)
        continue;
    if (!huiwen(i))
        continue;
    if (hwlength(i)%2==0&&i!=11)
    {
        i=extend(hwlength(i));
        continue;
    }
    if (prime(i))
        printf("%d\n",i);
}
return 0;

} 规律：任何长度为偶数的回文数字都是合数（除了11） 所以判断出来以后直接强行加一位就能省掉很多的时间

评论:

留个纪念，差两分破700

虚空终端 • 2年前 ……谢谢你的讨论，（我爱超时

耦园采雪 • 2年前 @虚空终端 你也是昆明湖的？几个朋友，我住翠微里

夏日里的萤火虫 • 4个月前 hint ​ © 2019 - 2025王码编程  滇ICP备19007937号-1如果您有任何问题，请联系我们 YNOIer@163.com您是本系统的第位访问者