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

许卿安 · 2025-04-12 17:08:51 · 题解

第 n 小的质数：B2085。第 2025 个质数是 17609。

从 2 开始暴力枚举每一个数是否质数即可。

如果一个数 x 为合数，那么它一定可以表示为 a\times b 的形式。不妨设 a\le b，那么 a\le\sqrt{x}。所以如果一个数除 1 外没有小于或等于 \sqrt{x} 的因子，那么这个数为质数。

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

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

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