题目描述：
小蓝有一个数 x，每次操作小蓝会选择一个小于 x 的素数 p，然后在 x 成为 p 的倍数前不断将 x 加 1，（如果 x 一开始就是 p 的倍数则 x 不变）。
小乔看到了小蓝进行了 2 次上述操作后得到的结果 n，他想知道 x 在一开始是多少。如果有多种可能，他想知道 x 一开始最小可以是多少，而如果不存在任何解，说明小乔看错了，此时请输出 −1。
输入格式
输入一行包含一个整数 n，表示经过两次操作后 x 的值。
输出格式
输出一行包含一个整数表示 x 的初始值。如果有多个解，输出最小的。如果不存在解，请输出 −1。
输入输出样例
输入 #1
22
输出 #1
8
说明/提示
【评测用例规模与约定】
- 对于 60% 的评测用例，1≤n≤5000；
- 对于所有评测用例，1≤n≤1e6。
蓝桥杯 2022 国赛 A 组 G 题。
解题思路：
我们先将题目简化一下，假设只求一次操作数后最小值。先拆解一下题目。首先这个输入数n是某个质数的k倍，那么这个初始数一定是在这个质数的k倍和（k-1）倍之间，因为若小于质数的（k-1）倍，在初始数不断++的过程中就会提前终止。同时题目又要求这个数为最小值，那么这个数就是输入数n的最大质因数+1。（我们暂且将其定义为x）
同理可得，我们通过第一次的计算算出了x，那么第二次的要找的操作数就在x和n之间，我们只需要依次算出他们的最大质因数，然后通过（操作数-最大质因数+1）的方法求得最小初始值。
举个例子如果说输入的数是39，那么它的最大质因数就是13，将39-13+1后得到27，那么第二次的操作数就在27,28,30,32,33,34,35,36,38之间产生。通过上面的方法我们一次对这些数进行运算，如法炮制，算出他们的最小初始值，然后进行比较得到整个数组的最小初始值，就能获得最终的最小操作数。上述的结果得到34的最大质因数17，34-17+1得到18，那么18就是初始值。
下面我们进行代码书写。
样例代码：
#include<iostream>
using namespace std;const int MAXN = 1000001;
int m, t; // m：输入数值，t：质数计数
bool isprime[MAXN];
int prime[MAXN]; // p存储质数
int p[MAXN]; // 存储某个数最大的质因数
int ans = 1e9; // 用来存储最小的符合条件的值// f函数用于计算给定的数字m的值，返回结果为 (m - p[m] + 1)
int f(int m)
{if (isprime[m] == true) // 如果m是质数{return 1e9; // 返回一个非常大的值}return (m - p[m] + 1); // 返回 (m 减去最大质因数 p[m] + 1)
}// 线性筛法（欧拉筛法）
// 用于筛出 1 到 m 之间的所有质数
void Linear_sieve()
{for (int i = 2; i <= m; i++) // 从 2 开始遍历到 m{isprime[i] = true; // 假设每个数都是质数}for (int i = 2; i <= m; i++) // 遍历每个数字{if (isprime[i]) // 如果当前数是质数{t++; // 质数计数器加 1prime[t] = p[i] = i; // prime[t] 存储当前质数 i，p[i] 存储 i}// 从当前质数 i 开始遍历后续数for (int j = 1; j <= t && i * prime[j] <= m; j++){p[i * prime[j]] = max(p[i], prime[j]); // 更新 i * prime[j] 的最大质因数isprime[i * prime[j]] = false; // 将 i * prime[j] 标记为合数if (i % prime[j] == 0) // 为了避免重复计算，减少多余的操作{break; // 如果 i 已经能被 prime[j] 整除，跳出循环，避免重复标记}}}
}int main()
{cin >> m;Linear_sieve(); // 通过线性筛法生成质数和更新其他数组// 下面的循环是为了找出最小的符合条件的数for (int i = f(m); i <= m; i++) // 循环从 f(m) 到 m{ans = min(ans, f(i)); // 计算 f(i)，并更新 ans 为最小值}// 如果 ans 被更新过，说明找到了符合条件的结果if (ans != 1e9){cout << ans << endl; // 输出最小的符合条件的值}else{cout << "-1" << endl; // 没有找到符合条件的值，输出 -1}return 0;
}代码解读：
我们首先遍历2到m的数，将它们假设为质数（true），那么后序我们只需要排除掉不是质数的数（false）。Linear_sieve()是欧拉筛法，用于筛选出质数，并且将每个数的最大质因数保存在p数组中。