B3750 题解

残阳如血 · 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;
}