专栏文章

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

MMasterArcherSkeleton
P12138题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipn1rqo
此快照首次捕获于
2025/12/03 14:41
3 个月前
此快照最后确认于
2025/12/03 14:41
3 个月前
查看原文

题意简化

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

正解思路

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

代码

CPP
#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;
        }
    }
}

我的提交记录

我的提交记录

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...