温馨提示：只有加了团的人才能看到题目哦

题目描述

如果一个数本身是素数，并且把最低位删除后得到的数仍是素数、再把最低位删除后得到的数仍是素数……如此往复，直到得到一个一位素数，我们就称它是“去尾素数”。

给出 $m$ 和 $n$ ，求 $m$ 到 $n$ 之间（包括 $m$ 和 $n$ ）所有的去尾素数。

输入格式

一行，两个整数 $m$ 和 $n$ 。

输出格式

若干行，所有 $m$ 到 $n$ 之间的去尾素数（按顺序输出）。

输入输出样例

输入 #1

1 10

输出 #1

2
3
5
7

输入 #2

20 50

输出 #2

23
29
31
37

算法1

(暴力枚举) $O(n\sqrt{n}\log_{10}(n))$

枚举从 $m$ 到 $n$ 的所有数，依次判断是否是去尾素数（注意： $1$ 不是素数）

时间复杂度

由于最多要枚举 $n$ 个数，每个数要判断是不是去尾素数最多需要 $\log_{10}(n)$ 次判断素数，每次判断素数需要 $O(\sqrt{n})$ 的时间，所以总共的时间复杂度就是 $O(n\sqrt{n}\log_{10}(n))$ 。

C++ 代码

#include <iostream>

using namespace std;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i ++ )
        if (!(x % i))
            return false;
    return true;
}

bool quwei(int x)
{
    if (!x) return true;
    return is_prime(x) && quwei(x / 10);
}

int main()
{
    int m, n;
    cin >> m >> n;

    for (int i = m; i <= n; i ++ )
        if (quwei(i))
            cout << i << '\n';

    return 0;
}

提交结果

时限10ms！是人做的吗？我好像在骂自己

算法2

(优化版暴力枚举) $O(n\log_{10}(n))$

用线性筛试试

时间复杂度

线性筛复杂度是 $O(n)$ ，最多要枚举 $n$ 个数，每个数要判断是不是去尾素数最多需要 $\log_{10}(n)$ 次判断素数，每次判断素数需要 $O(1)$ 的时间，所以总共的时间复杂度就是 $O(n\log_{10}(n))$ 。

C++ 代码

#include <iostream>

using namespace std;

const int N = 10000010;

int primes[N], cnt;
bool st[N] = {0, 1};

void init(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] * i <= n; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

bool quwei(int x)
{
    if (!x) return true;
    return !st[x] && quwei(x / 10);
}

int main()
{
    int m, n;
    cin >> m >> n;

    init(n);

    for (int i = m; i <= n; i ++ )
        if (quwei(i))
            cout << i << '\n';

    return 0;
}

提交结果

内存限制1MB！是人做的吗？我好像又在骂自己

算法3

(bfs) $O(4^{\log_{10}\ (x)}\sqrt{n})$

从一位去尾素数 $2,3,5,7$ 开始搜索，每次在后面分别添加 $1,3,7,9$ （因为所有多位去尾素数都以 $1,3,7,9$ 结尾），遇到在 $m$ 和 $n$ 之间并且是素数的就输出，一旦大于 $n$ 或不是素数了就停止拓展（别用线性筛，还记得MLE吗）
因为是bfs，是一位一位拓展的，只要按顺序搜就可以保证有序

时间复杂度

因为每次扩展四个数，所以搜到的数最多有 $4^{\log_{10}\ (x)}$ 个，素数判断最多需要 $O(\sqrt{n})$ 的时间，所以时间复杂度就是 $O(4^{\log_{10}\ (x)}\sqrt{n})$ （当然实际远比这小得多，因为不是素数的就不扩展了）

C++代码

#include <iostream>

using namespace std;

const int N = 10000010;

int digits[] = {1, 3, 7, 9};
int one_digit_primes[] = {2, 3, 5, 7};
int q[N];

int m, n;

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i * i <= x; i ++ )
        if (!(x % i))
            return false;
    return true;
}

void bfs()
{
    int hh = 0, tt = -1;
    for (auto p : one_digit_primes)
        q[ ++ tt] = p;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        if (t > n) continue;
        if (t >= m) cout << t << '\n';

        for (auto d : digits)
        {
            int x = t * 10 + d;
            if (x > n) continue;
            if (!is_prime(x)) continue;

            q[ ++ tt] = x;
        }
    }
}

int main()
{
    cin >> m >> n;

    bfs();

    return 0;
}

提交结果

终于……过了啊哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈（疯狂）

好了今天就讲到这里，再见啦ヾ(￣▽￣)Bye~