题解：P12138 [蓝桥杯 2025 省 A] 寻找质数

· · 题解

题意简化

求第 2025 小的质数。
题目链接

正解思路

首先，如果给定一个正整数 n(n \ge 2)，能否知道它是否是一个质数呢？
显然，因为 n \ge 2，所以 n 不是质数就是合数。
若 n 是一个合数（即 n 不是质数），则必存在正整数 p, q(p, q \ge 2)，使 n = pq。
不妨 p \le q，则必有 p \le \frac{n}{p}。
因为 p 是正数，所以两边同乘 p，得：p^2 \le n。
即：p \le \sqrt{n}。
所以，如果 n 是一个合数，就必然存在一个正整数 p，满足 2 \le p \le \sqrt{n}，且使 p \mid n（整除）。否则，即 n 是一个质数，那么就一定不存在这样的 p 了。
那么判断 n 是不是质数的方法就很明显了：尝试每一种 p 的可能即可。所以时间复杂度就是 \Omicron(\sqrt{n})。 但是问题求的是第 2025 小的质数，不过思路也很明显了：从 2 开始一直往上枚举 n，并判断它是否是质数。直到第 2025 个质数的时候就输出并结束程序即可。
那么，这个程序能否在规定时间内运行完毕呢？很简单，运行一下就好了——没有超时。

代码

#include <bits/stdc++.h>
using namespace std;
int n, p, cnt;
bool flag;
int main()
{
    for(n = 2, flag; ; ++n) {
        for(p = 2, flag = 0; p * p <= n; ++p) {
            if(n % p == 0) {
                flag = true;
                break;
            }
        }
        if(!flag) ++cnt;
        if(cnt == 2025) {
            cout << n;
            return 0;
        }
    }
}