Skip to content

1352: 有趣的数

题目

题目描述

小淦最近喜欢上了数论。为了展现她的与众不同,她决定命名一类特殊的数。具体地说,她想把一个数字称为“有趣的”。首先,这个数字必须是质数;其次,这个数正着读和反着读必须都一样。也就是说,这个数应该是一个回文数。

小淦不仅想知道一个数是不是有趣的数。她还想知道,在一个区间 $[l, r]$ 中到底有哪些有趣的数。你能帮帮她吗?

输入格式

输入一行两个整数 $l$, $r$

输出格式

从小到大输出有趣的数的列表,每行一个

样例输入

text 5 500

样例输出

text 5 7 11 101 131 151 181 191 313 353 373 383

数据范围

$5 \le a \le b \le 10^9$

Hint 1

如何判断一个数是素数?根据定义,我们只要保证它不被所有小于它的数整除即可。

但我们需要枚举所有小于它的数吗?如果一个数$n$不能被 $[2, \sqrt n]$ 的整数整除,它是否还可能被 $(\sqrt n, n)$ 的整数整除?

Hint 2

应该先找出所有的素数,还是找出所有的回文数?

只要确定了一半的位,我们就能确定一个回文数。

Hint 3 (Extra)

筛法是一类可以求出 $1 \sim n$ 之间所有素数的算法。常见的筛法包括时间复杂度 $O(n)$ 的线性筛、 $O(n \log\log n)$ 的埃拉托斯特尼筛法等。

有时间的同学,不妨试一试用筛法过掉这道题。不过,本题对算法实现的常数要求较高~

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!