一、 埃氏筛 (Sieve of Eratosthenes)

这是最基础、最符合直觉的筛法。

• 算法流程：

1. 假设所有数都是质数。
2. 从 2 开始从小到大遍历，如果遇到一个质数 $i$，就把它的所有倍数（$i \times i, i \times (i+1) \dots$）全都标记为合数。

• 适用场景：

• 求 $1 \sim N$ 的质数（但速度不如线性筛）。

• 核心特长：由于它是枚举质数的倍数，所以非常适合在筛的过程中，顺便求出每个数的所有质因子，或者处理某些非积性函数。

• 时间复杂度：$O(N \log \log N)$

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

const int N = 1000005;
bool is_prime[N];
int primes[N], cnt;

void eratosthenes(int n) {
    // 1. 初始化全为质数
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    
    // 2. 从 2 开始遍历
    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            primes[cnt++] = i; // 记录质数
            // 3. 将 i 的倍数标记为合数，从 i*i 开始优化（因为更小的倍数已被更小的质数筛去）
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = 0;
            }
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    eratosthenes(100);
    return 0;
}

---

二、 线性筛 / 欧拉筛 (Euler's Sieve)

竞赛绝对主力，也是你必须肌肉记忆的模板。

• 算法流程：

1. 假设所有数都是质数。
2. 遍历 $2 \sim N$：如果是质数，加入质数表。
3. 遍历已知质数表，将 当前数 * 质数 标记为合数。
4. 灵魂一步：如果当前数能被该质数整除，立刻 break。保证每个合数只被它的最小质因数筛掉一次。

• 适用场景：

• 快速求 $1 \sim N$ 的所有质数。

• 核心特长：结合 break 的性质，极其适合线性求各种积性函数（如欧拉函数 $\phi$、莫比乌斯函数 $\mu$、约数个数等）。

• 时间复杂度：绝对严格的 $O(N)$

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

const int N = 1000005;
bool is_prime[N];
int primes[N], cnt;

void linear_sieve(int n) {
    memset(is_prime, 1, sizeof(is_prime));
    is_prime[0] = is_prime[1] = 0;
    
    for (int i = 2; i <= n; i++) {
        // 发现质数
        if (is_prime[i]) primes[cnt++] = i;
        
        // 遍历已知质数
        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
            is_prime[i * primes[j]] = 0; // 筛掉合数
            
            // 遇到最小质因数，立刻停止，防止重复筛选
            if (i % primes[j] == 0) break;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    linear_sieve(100);
    return 0;
}

---

根据数论基础：如果一个数 $X \le U$ 是合数，那么它必定有一个质因数 $P \le \sqrt{U}$。 因为 $\sqrt{2^{31}-1} \approx 46340$，所以我们只需要： 第一步（预处理）：用线性筛求出 $1 \sim 50000$ 范围内的所有质数。 第二步（区间筛）：对于每组输入的 $L$ 和 $U$，遍历我们预处理出的质数 $P$。算出在 $[L, U]$ 区间内 $P$ 的倍数，把它们全部标记为合数。为了不爆内存，我们将下标平移，用 is_p[i - L] 来代表数字 i 是否为合数。 第三步（统计）：遍历平移后的标记数组，记录相邻两个质数的差值，不断更新最大值和最小值即可。

樱花

一、 数学等式推导

我们的目标是求不定方程 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$ 的正整数解 $(x, y)$ 的数目。为了方便处理，我们需要将分式化为整式。

1. 去分母：

   等式两边同时乘以 $x \cdot y \cdot n!$，得到：

   $$y \cdot n! + x \cdot n! = x \cdot y$$

2. 移项与因式分解：

   将所有项移到等号一侧，得到：

   $$x \cdot y - x \cdot n! - y \cdot n! = 0$$

   为了把等式左侧凑成可以因式分解的形式，我们在等式两边同时加上 $(n!)^2$：

   $$x \cdot y - x \cdot n! - y \cdot n! + (n!)^2 = (n!)^2$$

   此时，等号左边可以提取公因式，完美地分解为：

   $$(x - n!)(y - n!) = (n!)^2$$

3. 分析解的对应关系：

   由于题目要求 $x$ 和 $y$ 均为正整数，并且 $\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$，显然必然有 $\frac{1}{x} < \frac{1}{n!}$（因为 $\frac{1}{y} > 0$），这就意味着推导出了边界条件：$x > n!$ 且 $y > n!$。

   我们可以令 $A = x - n!$，$B = y - n!$。既然 $x, y > n!$，那么 $A$ 和 $B$ 必定都是正整数。

   此时原方程变为了：

   $$A \cdot B = (n!)^2$$

   这说明，只要我们能找到 $(n!)^2$ 的任意一个正约数 $A$，就可以唯一确定一个正约数 $B$，进而唯一对应确定一组符合题意的正整数解 $(x, y)$。

   满足条件的正整数解 $(x, y)$ 的对数，完全等于 $(n!)^2$ 的正约数个数。

二、 约数个数求法推导

根据算术基本定理（唯一分解定理），如果我们将一个整数分解为质因数的乘积形式 $p_1^{a_1} \cdot p_2^{a_2} \cdots p_k^{a_k}$，那么它的正约数个数为：

$$(a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$$

假设 $n!$ 质因数分解后，质因子 $p_i$ 的指数为 $c_i$，那么 $(n!)^2$ 中质因子 $p_i$ 的指数就是 $2 \cdot c_i$。因此 $(n!)^2$ 的正约数总个数为：

$$\prod_{i=1}^{k} (2c_i + 1)$$

如何快速求 $n!$ 中各个质因子的指数？

利用勒让德公式 (Legendre's Formula)，阶乘 $n!$ 中包含质因子 $p$ 的个数 $c_p$ 可以通过不断将 $n$ 除以 $p$ 的幂次方并向下取整求和来计算：

$$c_p = \sum_{j=1}^{\infty} \left\lfloor \frac{n}{p^j} \right\rfloor$$

反素数

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

// n: 题目给定的上限
// mxd: 搜索过程中记录的最大约数个数
// ans: 对应的最大反素数数值
// p数组: 前10个质数。因为 2*3*5*7*11*13*17*19*23*29 > 2*10^9，所以最多只需要用到前10个质数！
int n, mxd, ans, p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};

/*
 * dfs参数释义：
 * u   : 当前正在枚举第 u 个质数
 * val : 当前累乘得到的数值
 * d   : 当前数值的约数总个数（根据约数个数定理累乘得到）
 * lim : 当前质数能够枚举的指数上限
 */
void dfs(int u, int val, int d, int lim) {
    // 【核心数论性质 1】：更新最优解
    // 1. 如果约数个数 d 更大，毫无疑问更新答案。
    // 2. 如果约数个数 d 一样大，为什么取更小的 val？
    //    因为反素数定义是：比它小的所有数的约数个数都严格小于它。
    //    如果存在 val1 < val2 且约数个数相同，那么 val2 绝对不可能是反素数！
    //    所以我们要找的，其实是“在产生最大约数个数时，数值最小的那个数”。
    if (d > mxd || (d == mxd && val < ans)) {
        mxd = d;
        ans = val;
    }
    
    // 【剪枝】：用到第11个质数必然超出 2e9，直接回溯
    if (u > 10) return;
    
    int t = val;
    
    // 【核心数论性质 2】：反素数的质因子指数必须单调不增！
    // 假设存在 2^3 * 3^4，它的约数个数和 2^4 * 3^3 一样多，但前者数值更大，必定不是反素数。
    // 所以 p[u] 的指数 i，绝对不能超过 p[u-1] 的指数 lim。
    for (int i = 1; i <= lim; i++) {
        if (t * p[u] > n) break; // 数值超过上限 n，直接剪枝
        
        t *= p[u];
        
        // 走向下一层：下个质数是 u+1，数值变大为 t，约数个数乘以 (i+1)，下一个指数的上限限制为当前的 i
        dfs(u + 1, t, d * (i + 1), i);
    }
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    
    // 初始调用：从第1个质数(2)开始，初始值为1，约数个数为1。
    // 指数上限给 31，因为 2^31 > 2*10^9，这是能达到的绝对极限。
    dfs(1, 1, 1, 31);
    
    cout << ans << '\n';
    return 0;
}