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

GSQ0829 · 2025-04-12 19:52:57 · 题解

前置知识：质数

什么是质数？

质数就是在大于一的自然数中，除了一和该数自身外，无法被其他自然数整除的数就称为质数。

比如 2、5、79、103 等等。

解题思路：

入门题。

因为，题目只让我们找到第 2025 个质数。显然这个数不会太大，只需要用暴力枚举的方法就可以了。

首先，我们要写出一个判断是否是质数的函数。

bool isPrime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

然后，我们需要一个计数器，来统计当前到了第几个质数。只要当前这个数字是质数，计数器就加一。再判断如果计数器达到了 2025，也就是已经找到了第 2025 个质数，就输出当前这个数字。

for (int i = 2;; i++) {
    if (isPrime(i)) ans++;
    if (ans == 2025) {
        cout << i;
        return 0;
    }
}

最后算出来答案为 17609。

代码：

这里给出两个代码。

第一种，是详细的解法。

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

bool isPrime(int x) {
    if (x < 2) return 0;
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) return 0;
    }
    return 1;
}

int ans;

int main() {
    for (int i = 2;; i++) {
        if (isPrime(i)) ans++;
        if (ans == 2025) {
            cout << i;
            return 0;
        }
    }
    return 0;
}

第二种，是直接输出答案。

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

int main() {
    cout << 17609;
    return 0;
}