自动搬运

查看原文

来自洛谷，原作者为

	残阳如血 人事已尽，天命难违

搬运于2025-08-24 21:14:48，当前版本为作者最后更新于2023-09-27 20:15:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路分析

直接模拟即可。

我们需要 $\mathcal O(\sqrt{n})$ 的时间判断一个数是否为质数（当然如果你有强迫症也可以用质数筛），$\mathcal O(\log n)$ 的时间扫描完一个数字，所以总的时间复杂度就是 $\mathcal O(n\log n\,\sqrt{n})$，能够通过本题。

代码演示

可以看注释理解。

#include <iostream>

bool isPrime(int x) { // 判断是否为质数
	if (x < 2) return false;
	for (int mod = 2; mod * mod <= x; ++mod)
		if (!(x % mod)) return false;
	return true;
}

bool check(int x) {
	while (x) {
		if (!isPrime(x)) return false;
		x /= 10; // 按位分解，这部操作相当于去掉一个数的最后一位
	}
	return true;
}

int main() {
	int m, n; std::cin >> m >> n;
	for (int i = m; i <= n; ++i)
		if (check(i)) std::cout << i << '\n';
	return 0;
}