Acwing 5367. 不合群数

题面：
如果一个正整数无法被 \([2,a]\) 范围内的任何整数整除，则称其为不合群数。
请你计算并输出 \([2,b]\) 范围内的最大不合群数。
提示：\(10\) 亿内的最大质数是 \(999999937\)，且相邻质数之间的差值均不超过 \(300\)

原题链接：5367. 不合群数 - AcWing

根据给出的提示判断可以使用试除法暴力枚举：
若某数为质数，则其一定是不合群数（反之不一定成立）。
需要输出的是范围内最大的不合群数，即从终点开始枚举；
而相邻质数之间差值不超过 \(300\)，说明最多枚举 \(300\) 步即可。
此外，枚举范围不一定是 \([2,a]\)，有时枚举到 \(sqrt(i)\) 即可。
故时间复杂度：\(O(n)=300 \times \sqrt{9e^8}=3e^2\times3e^4=10^7\)

附录 - y总的神秘小诀窍：由数据范围反推算法复杂度以及算法内容 - AcWing

1. \(n \leq 30\)，指数级别, dfs+剪枝，状态压缩dp
2. \(n \leq 100\)，\(O(n^3)\)，floyd，dp，高斯消元
3. \(n \leq 1000\)，\(O(n^2)\)，\(O(n^2\log n)\)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
4. \(n \leq 10000\)，\(O(n *\sqrt{n})\)，块状链表、分块、莫队
5. \(n \leq 100000\)，\(O(n\log n)\)，各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树
6. \(n \leq 1000000\)，\(O(n)\)，以及常数较小的 \(O(n\log n)\) 算法，单调队列、hash、双指针扫描、BFS、并查集，kmp、AC自动机，常数比较小的 \(O(n\log n)\) 的做法：sort、树状数组、heap、dijkstra、spfa
7. \(n \leq 10000000\)，\(O(n)\)，双指针扫描、kmp、AC自动机、线性筛素数
8. \(n \leq 10^9\)，\(O(\sqrt{n})\)，判断质数
9. \(n \leq 10^{18}\)，\(O(\log n)\)，最大公约数，快速幂，数位DP
10. \(n \leq 10^{1000}\)，\(O((\log n)^2)\)，高精度加减乘除
11. \(n \leq 10^{100000}\)，\(O(\log k \cdot \log \log k)\)，\(k\) 表示位数，高精度加减、FFT/NTT

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int a, b;
	cin >> a >> b;
	for (int i = b; i > a; i--) {
		bool flag = true;
		for (int j = 2; j <= a && j <= sqrt(i); j++) {
			if (!(i % j)) {
				flag = false;
				break;
			}
		}
		if (flag) {
			cout << i;
			return 0;
		}
	}
	cout << "-1";
	return 0;
}