正经题解｜质数花瓣

题目大意

在一个长度为 $n$ 的数字区间内，寻找符合要求的质数。

题意分析

如果每次去掉数字的最后一位，仍是质数，则满足要求

解题思路

素数筛模板题，可以套用埃氏筛或欧拉筛

如果你的埃氏筛超时了，请将标记数组换成bitset容器

如果你的欧拉筛超内存了，请将数据类型换成short

当然此题不止这一种解法，你还可以按数字位搜索，找到符合条件的数。

时间复杂度

时间复杂度为：$O(n\log\log n)$

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1e8 + 10;
bitset<N> st;
void get(int r) {
    st[1] = 1;
    for(int i=2;i<=r/i;i++) {
        if (st[i])continue;
        for(int j=i*i;j<=r;j+=i) {
            st[j] = 1;
        }
    }
}
int main() {
    int n;
    cin >> n;
    int l = pow(10,n-1),r = pow(10,n);
    get(r);
    for(int i=l;i<r;i++) {
       int f = 1;
       int x = i;
       while(x) {
           if (st[x]) {
               f = 0;
               break;
           }
           x /= 10;
       }
       if (f)cout << i << endl;
    }
    return 0;
}