P12138 题解

RyanLi · 2025-04-12 17:16:20 · 题解

传送门：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} 可以用积分上下界估计，有：

计算积分：

因此有下界 \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}}，因此上界可近似为：

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