第十六届蓝桥杯省赛 C/C++ 大学 A 组真题解析

题目一：寻找质数

题目描述

本题的目标是枚举质数并计数，直到数到第 2025 个。由于 2025 不算太大，第 2025 个质数大约在 17000~18000 之间，完全可以在合理时间内通过简单枚举得到。

解题步骤

从 2 开始遍历每个整数，判断它是否是质数。质数判断采用试除法：对于一个数 n，只需检查从 2 到√n 的所有整数是否能整除 n。若存在能整除的数，则 n 不是质数；否则是质数。每找到一个质数，计数器加 1。当计数器达到 2025 时，输出当前的质数并结束。 优化点：除了 2 以外，偶数不可能是质数，因此可以跳过偶数判断（直接步进 2）。

C++ 参考代码

#include <iostream>
#include <cmath>
using namespace std;

// 判断一个整数是否为质数
bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false; // 偶数直接排除
    int limit = sqrt(n); // 只需检查到平方根
    for (int i = 3; i <= limit; i += 2) { // 只检查奇数因子
        if (n % i == 0) return false;
    }
    return true;
}

int main {
     count = ; 
     num = ; 
     () {
         ((num)) {
            count++;
             (count == ) {
                cout << num << endl;
                ;
            }
        }
        num++;
    }
     ;
}