传送门：P12138 [蓝桥杯 2025 省 A] 寻找质数

更佳的阅读体验：洛谷 P12138 题解

简要题意：求第 $2025$ 个质数。

我们知道，对于一个数 $x$，判断其是否为质数的时间复杂度为 $\Theta (\sqrt{x})$。如果只是求第 $2025$ 个质数，那么我们考虑从 $2$（最小的质数）开始，对每个数都判断一遍是否为质数，直到第 $2025$ 个质数。

接下来讨论这个算法的可行性。直接的时间复杂度是 $\Theta (\sum \limits_{x = 1}^{n} \sqrt{x})$，其中 $n = 2025$。我们很难估计其数量级，因此我们考虑计算 $2025 \times \sqrt{2025} \approx 10^5$ ——该算法的效率可以接受。

事实上，第 $n$ 个质数的大小量级约为 $O(n \log n)$，如果你知道这点，那么就可以很容易地判断出该算法的可行性了。

#include <iostream>
using namespace std;

int cnt;

bool prime(int x) {
    for (int i = 2; i * i <= x; ++i)
        if (!(x % i)) return false;
    return true;
}

int main() {
    for (int i = 2;; ++i) {
        cnt += prime(i);
        if (cnt == 2025) {
            cout << i << '\n';
            break;
        }
    } return 0;
}

到这里，本篇题解的核心部分已经结束。接下来我们来更精确地讨论一下上述算法的时间复杂度。

要化简复杂度表达式 $\Theta (\sum \limits_{x = 1}^{n} \sqrt{x})$，我们可以使用积分进行近似。对于单调递增函数 $f(x) = \sqrt{x}$，其和 $\sum \limits_{x = 1} ^ n \sqrt{x}$ 可以用积分上下界估计，有：

$$ \int_{0}^{n} \sqrt{x} \, dx \leq \sum \limits_{x = 1}^n \sqrt{x} \leq \int_{1}^{n + 1} \sqrt{x} \, dx $$

计算积分：

$$ \int \sqrt{x} \, dx = \dfrac{2}{3} x^{\tfrac{3}{2}} $$

因此有下界 $\displaystyle \int_{0}^{n} \sqrt{x} \, dx = \dfrac{2}{3} n^{\tfrac{3}{2}}$ 和上界$\displaystyle \int_{1}^{n + 1} \sqrt{x} \, dx = \dfrac{2}{3}(n + 1)^{\tfrac{3}{2}} - \dfrac{2}{3}$。

当 $n \to \infty$ 时，$(n+1)^{\tfrac{3}{2}} \approx n^{\tfrac{3}{2}} + \dfrac{3}{2} n^{\tfrac{1}{2}}$，因此上界可近似为：

$$ \frac{2}{3}n^{\tfrac{3}{2}} + \mathcal{O}(n^{\tfrac{1}{2}}) $$

忽略低阶项后，上下界均为 $\Theta(n^{\tfrac{3}{2}})$。因为本题中 $n = 2025$，所以复杂度可以接受。