[蓝桥杯][算法提高VIP]特殊的质数肋骨

题目

题目链接

题解

两种方法，一种是直接打表，保存下数，之后直接输出；另一种是稍微思考一下，根据输入计算再输出。

第一种： 通过欧拉筛，选出素数，暴力枚举每个数判断是不是特殊质数。

第二种： i位的特殊质数的前缀一定是i-1位的特殊质数。 一位的特殊质数有：2 3 5 7，那么两位的特殊质数的格式为：2X 3X 5X 7X，其中X可能为0~9； 但还可以进一步缩小X的范围，偶数必然不是质数，结尾是5的数也不是，因此X的范围变为了1 3 7 9。 我们只需要在求出i-1位的特殊质数后，在这些特殊质数后加上1 3 7 9作为个位，再通过O(√n)的判素数算法判断构成的数是否为特殊质数，若是则记录下来，这就求出来全部的i位特殊质数了，接下来的i+1位同理递推。

代码1

// 打表代码
#include
using namespace std;
const int N = 1e8+10;

int prime[N], vis[N], cnt;

int main()
{
	vis[1] = 1;
	for(int i = 2;i